Python 2.7中高效获取两列表差值在[-21,21]的索引对方法

Hey there! Let's break down the best way to solve this problem in Python 2.7—especially since you're dealing with large lists, brute force just won't cut it for performance.

First, let's get one thing straight: a naive nested loop (checking every pair of elements) will have O(N*M) time complexity, which is totally impractical for large datasets. We need a more efficient approach, ideally with a time complexity of O((N + M) log(N + M)) or similar.

Approach 1: Binary Search with Pre-sorted List2 #

This works great if one of your lists is significantly smaller than the other, or if you prefer a straightforward implementation using Python's built-in bisect module (which is available in Python 2.7).

How it works: #

1. Preprocess list2 by sorting its elements along with their original indices. This lets us quickly find ranges of elements that fall within your target difference range.
2. For each element in list1, calculate the lower (val1 - 21) and upper (val1 + 21) bounds for matching elements in list2.
3. Use binary search to find the start and end positions of elements in the sorted list2 that fit within these bounds.
4. Collect all valid (list1 index, list2 index) pairs from this range.

Code Implementation: #

import bisect

def find_matching_pairs(list1, list2):
    # Preprocess list2: sort values while keeping track of original indices
    sorted_list2 = sorted((val, idx) for idx, val in enumerate(list2))
    sorted_values = [val for val, idx in sorted_list2]
    results = []
    
    for list1_idx, val1 in enumerate(list1):
        lower = val1 - 21
        upper = val1 + 21
        
        # Find the first index in sorted_list2 where value >= lower
        left_pos = bisect.bisect_left(sorted_values, lower)
        # Find the first index in sorted_list2 where value > upper
        right_pos = bisect.bisect_right(sorted_values, upper)
        
        # Iterate over all matching elements and collect pairs
        for pos in xrange(left_pos, right_pos):
            val2, list2_idx = sorted_list2[pos]
            # Option 1: Store index pairs
            results.append((list1_idx, list2_idx))
            # Option 2: Store formatted string with difference
            # results.append("diff: {}, list1_index = {}, list2_index = {}".format(val1 - val2, list1_idx, list2_idx))
    
    return results

# Test with your sample data
list1 = [0, 10, 20]
list2 = [0, 10, 20, 30, 40, 50]
matches = find_matching_pairs(list1, list2)
for match in matches:
    print(match)

Approach 2: Two-Pointer Technique with Sorted Lists #

If both lists are extremely large, this method can be more efficient than repeated binary searches. It works by sorting both lists (with their indices) and then traversing them with two pointers to find valid pairs in linear time after sorting.

How it works: #

1. Sort both list1 and list2 along with their original indices.
2. Use two pointers to traverse the sorted lists:
   • If the current element pair's difference is within [-21, 21], collect all valid pairs from list2 for this list1 element (since the list is sorted, we can keep moving the list2 pointer until we exceed the upper bound).
   • If the difference is too small (val1 < val2 -21), move the list1 pointer forward to get a larger value.
   • If the difference is too large (val1 > val2 +21), move the list2 pointer forward to get a larger value.

Code Implementation: #

def find_matching_pairs_two_pointers(list1, list2):
    # Sort both lists while preserving original indices
    sorted_list1 = sorted((val, idx) for idx, val in enumerate(list1))
    sorted_list2 = sorted((val, idx) for idx, val in enumerate(list2))
    
    results = []
    i = j = 0
    len1, len2 = len(sorted_list1), len(sorted_list2)
    
    while i < len1 and j < len2:
        val1, idx1 = sorted_list1[i]
        val2, idx2 = sorted_list2[j]
        diff = val1 - val2
        
        if -21 <= diff <= 21:
            # Collect this pair, then check subsequent elements in list2
            results.append((idx1, idx2))
            temp_j = j + 1
            while temp_j < len2:
                temp_val2, temp_idx2 = sorted_list2[temp_j]
                if temp_val2 <= val1 + 21:
                    results.append((idx1, temp_idx2))
                    temp_j += 1
                else:
                    break
            # Move to next element in list1
            i += 1
        elif diff < -21:
            # val1 is too small, need a larger value from list1
            i += 1
        else:
            # val2 is too small, need a larger value from list2
            j += 1
    
    return results

# Test the two-pointer method
matches = find_matching_pairs_two_pointers(list1, list2)
for match in matches:
    print(match)

Which Approach to Choose? #

• Use Binary Search if one list is much smaller than the other, or if you want a simpler implementation.
• Use Two-Pointer if both lists are very large and you want to minimize the number of operations after sorting.

Both methods avoid the O(N*M) brute force trap and will handle large datasets efficiently in Python 2.7.

内容的提问来源于stack exchange，提问作者m.i.cosacak