求二进制数组中所有1移至一处的最少交换次数（O(n)/O(nlogn)解法）

Alright, let's break down this problem: we have a binary array (only 0s and 1s), and we need to rearrange it so all the 1s form a single consecutive block. The goal is to find the minimum number of adjacent swaps needed to do this—just like your example where [0,1,0,1,1,0,0] becomes [0,0,1,1,1,0,0] in exactly 1 swap.

Core Idea: Use the Median for Minimal Distance #

The key insight here is that when you want to gather elements into a consecutive block with minimal movement (which directly translates to minimal adjacent swaps), the optimal center point is the median of the positions of the 1s. This is because the median minimizes the sum of absolute distances to all points—exactly what we need, since each adjacent swap moves a 1 one position closer to its target.

Step-by-Step Breakdown #

1. Collect positions of all 1s: First, iterate through the array and note down every index where there's a 1. Let's call this list ones_positions.
2. Handle edge cases: If there are 0 or 1 ones, we don't need any swaps—return 0 right away.
3. Find the median position: Grab the middle element of ones_positions; this will be our anchor point for grouping the 1s.
4. Calculate total swaps: For each 1, compute how far it needs to move to reach its spot in the consecutive block (relative to the median). Sum those distances, and that's our minimal swap count.

Let's test this with your example:

• Original array: [0,1,0,1,1,0,0]
• ones_positions = [1, 3, 4]
• Median position is 3 (the middle element of the list)
• For the first 1 at index 1: it needs to move to 3 - (1 - 0) = 2 → distance of 1
• The second 1 is already at the median position (3) → distance 0
• The third 1 is at 4, which is exactly where it needs to be (3 + (2 - 1) = 4) → distance 0
• Total swaps: 1 + 0 + 0 = 1. Perfect, matches your example!

Python Code Implementation #

def min_swaps_group_ones(arr):
    # Collect all indices where the element is 1
    ones_pos = []
    for idx, num in enumerate(arr):
        if num == 1:
            ones_pos.append(idx)
    
    num_ones = len(ones_pos)
    # No swaps needed if there's 0 or 1 one
    if num_ones <= 1:
        return 0
    
    # Find the median position of the 1s
    median_idx = num_ones // 2
    median_pos = ones_pos[median_idx]
    
    total_swaps = 0
    for i in range(num_ones):
        # Target position for the i-th 1 is median_pos shifted by (i - median_idx)
        target = median_pos + (i - median_idx)
        total_swaps += abs(ones_pos[i] - target)
    
    return total_swaps

# Test with your example
test_arr = [0,1,0,1,1,0,0]
print(min_swaps_group_ones(test_arr))  # Output: 1

Time Complexity #

This runs in O(n) time:

• We loop through the array once to collect 1 positions: O(n)
• We loop through the list of 1 positions (which is at most n elements) to calculate swaps: O(k) where k ≤ n
• Combined, this is linear time, which meets your requirement.

Quick Note on Non-Adjacent Swaps #

If the problem allowed swapping any two elements (not just adjacent), the minimal swap count would be total_ones - length_of_longest_consecutive_ones. But since your example aligns with adjacent swaps, the median-based approach is the right fit here.

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