基于Numpy实现一维数组拼接并合并重叠首尾的高效方案问询

Great question! Iterating element-wise gets the job done, but we can leverage NumPy's vectorized operations to build a cleaner, more efficient solution. The goal is to find the longest suffix-prefix overlap between two arrays, then merge them to produce the shortest possible array that ends with the second input array.

Approach #

The core logic breaks down into these steps:

1. Handle edge cases: Return the non-empty array if either input is empty.
2. Find the longest valid overlap: Check from the largest possible overlap length (the size of the smaller array) down to 1, looking for a match between the suffix of array A and the prefix of array B.
3. Merge or concatenate: If an overlap is found, combine A (excluding the overlapping suffix) with B. If no overlap exists, simply concatenate the full arrays.

Solution Code #

import numpy as np

def smart_merge(A, B):
    # Convert inputs to NumPy arrays (works with lists too)
    A = np.asarray(A)
    B = np.asarray(B)
    
    # Edge case: return the non-empty array if one is empty
    if A.size == 0:
        return B
    if B.size == 0:
        return A
    
    max_possible_overlap = min(A.size, B.size)
    
    # Check from largest possible overlap down to 1
    for k in range(max_possible_overlap, 0, -1):
        # Compare the last k elements of A with first k elements of B
        if np.array_equal(A[-k:], B[:k]):
            # Merge: take A without overlapping suffix, append B
            return np.concatenate([A[:-k], B])
    
    # No overlap found: concatenate full arrays
    return np.concatenate([A, B])

Testing the Examples #

Let's validate with your sample inputs:

• Example 1: A = [1, 2, 4], B = [2, 4, 5]

  print(smart_merge([1,2,4], [2,4,5]))  # Output: [1 2 4 5]
  

  The longest overlap is 2 elements ([2,4]), so we drop the last 2 elements of A and append B.

• Example 2: A = [1, 2, 4], B = [2, 5, 4]

  print(smart_merge([1,2,4], [2,5,4]))  # Output: [1 2 4 2 5 4]
  

  No matching suffix-prefix pairs exist, so we concatenate the full arrays.

• Example 3: A = [1, 2, 4], B = [1, 2, 4, 5]

  print(smart_merge([1,2,4], [1,2,4,5]))  # Output: [1 2 4 5]
  

  The entire A matches the prefix of B, so we just return B.

Why This Works #

• We prioritize the longest overlap first, ensuring the merged array is as short as possible.
• np.array_equal uses vectorized comparisons, which is faster than manual element-wise loops for larger arrays.
• The function accepts both lists and NumPy arrays as inputs, making it flexible.

内容的提问来源于stack exchange，提问作者Vidak