Lily的家庭作业（Hackerrank）：生成最美数组的最少交换次数测试用例失败排查

Hey there! Let's break this down step by step so George can help Lily finish that homework fast and get out to play. 😎

The problem says a "most beautiful array" is one where the sum of absolute differences between adjacent elements is as small as possible. If you think about it, this only happens when the array is sorted in either ascending or descending order. Why? Because sorted arrays have the closest possible adjacent values—no big jumps between elements, which keeps that sum minimized.

For example, take [3,1,2]:

• Ascending sorted: [1,2,3] → sum of differences is 1 + 1 = 2
• Descending sorted: [3,2,1] → sum is also 1 + 1 = 2
  Both are equally "beautiful," but we need to check which one requires fewer swaps to reach from the original array.

The core of this problem is a classic algorithm question: finding the minimum number of swaps needed to turn an array into a sorted target. Here's how it works using permutation cycles:

1. Map each element in the original array to its position in the target sorted array (since all elements are unique, this mapping is one-to-one).
2. Find cycles in this permutation: a cycle is a sequence of elements where each element is in the position of the next element in the cycle, and the last element loops back to the first.
3. The minimum number of swaps for a cycle of length k is k - 1. For the whole array, total swaps = total elements - number of cycles.

Let's take an example: original array [4,3,2,1], target ascending sorted array [1,2,3,4]

• The permutation mapping is: 4 → index 3, 3 → index 2, 2 → index 1, 1 → index 0
• Cycles:
  • Index 0 → 3 → 0 (cycle length 2)
  • Index 1 → 2 → 1 (cycle length 2)
• Total swaps = 4 - 2 = 2 (swap 0&3, swap1&2—done!)

It's easy to assume ascending order is the only target, but sometimes descending order might require fewer swaps. For example, take the array [1,2,3,5,4]:

• Ascending sort only needs 1 swap (swap 5 and 4)
• Descending sort would need 3 swaps to turn it into [5,4,3,2,1]
  So we have to calculate swap counts for both ascending and descending targets, then pick the smaller number.

Here's a clean, commented code snippet that puts this all together:

def count_required_swaps(original, target):
    # Create a map from each element to its index in the target array
    element_to_target_idx = {num: idx for idx, num in enumerate(target)}
    visited = [False] * len(original)
    total_swaps = 0

    for i in range(len(original)):
        if not visited[i]:
            cycle_length = 0
            current = i
            # Traverse the entire cycle
            while not visited[current]:
                visited[current] = True
                # Move to the position where the current element should be
                current = element_to_target_idx[original[current]]
                cycle_length += 1
            # Add swaps needed for this cycle (only if cycle length > 1)
            if cycle_length > 1:
                total_swaps += cycle_length - 1
    return total_swaps

def min_swaps_for_beautiful_array(arr):
    n = len(arr)
    if n <= 1:
        return 0  # No swaps needed for empty or single-element arrays
    
    # Generate both possible target arrays
    ascending_target = sorted(arr)
    descending_target = sorted(arr, reverse=True)
    
    # Calculate swaps for both targets
    swaps_asc = count_required_swaps(arr, ascending_target)
    swaps_desc = count_required_swaps(arr, descending_target)
    
    # Return the smaller swap count
    return min(swaps_asc, swaps_desc)

# Test it out!
test_arr1 = [4, 3, 2, 1]
print(min_swaps_for_beautiful_array(test_arr1))  # Output: 2

test_arr2 = [1,2,3,5,4]
print(min_swaps_for_beautiful_array(test_arr2))  # Output: 1

test_arr3 = [3,1,2]
print(min_swaps_for_beautiful_array(test_arr3))  # Output: 1

• Since all elements are distinct, we don't have to worry about duplicate mappings—each element has exactly one correct position in the target array.
• Always handle edge cases: empty arrays or single-element arrays need 0 swaps.
• Never skip checking the descending sorted target—it can save you extra swaps in some cases!

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