计算将序列排序所需的最小交换次数

#include<bits/stdc++.h>
using namespace std;


int main()
{
    int n,i,j,k,num = 0;
    cin >> n;
    int arr[n+1];
    for(i = 1;i <= n;++i)cin >> arr[i];
    for(i = 1;i <= n;++i)
    {
        if(i != arr[i])// condition to check if an element is in a cycle r nt
        {
            j = arr[i];
            arr[i] = 0;
            while(j != 0)// Here i am traversing a cycle as mentioned in 
            {             // first answer
                k = arr[j];
                arr[j] = j;
                j = k;
                num++;// reducing cycle by one node each time
            }
            num--;
        }
    }
    for(i = 1;i <= n;++i)cout << arr[i] << " ";cout << endl;
    cout << num << endl;
    return 0;
}

使用JavaScript的解决方案。

首先，我将需要排序的所有元素与它们当前的索引设置好，然后我遍历映射表，仅对需要交换的元素进行排序。

function minimumSwaps(arr) {
  const mapUnorderedPositions = new Map()
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] !== i+1) {
      mapUnorderedPositions.set(arr[i], i)
    }
  }

  let minSwaps = 0
  while (mapUnorderedPositions.size > 1) {
    const currentElement = mapUnorderedPositions.entries().next().value
    const x = currentElement[0]
    const y = currentElement[1]

    // Skip element in map if its already ordered
    if (x-1 !== y) {
      // Update unordered position index of swapped element
      mapUnorderedPositions.set(arr[x-1], y)

      // swap in array
      arr[y] = arr[x-1]
      arr[x-1] = x

      // Increment swaps
      minSwaps++
    }

    mapUnorderedPositions.delete(x)
  }


  return minSwaps
}

Map { 7 => 0, 4 => 2, 3 => 3, 1 => 6 }
currentElement [ 7, 0 ]
swapping 1 with 7
[ 1, 2, 4, 3, 5, 6, 7 ]

currentElement [ 4, 2 ]
swapping 3 with 4
[ 1, 2, 3, 4, 5, 6, 7 ]

currentElement [ 3, 2 ]
skipped

minSwaps = 2

Go版本1.17：

func minimumSwaps(arr []int32) int32 {

var swap int32
for i := 0; i < len(arr) - 1; i++{
    for j := 0; j < len(arr); j++ {
        if arr[j] > arr[i] {
            arr[i], arr[j] = arr[j], arr[i]
            swap++
        }else {
        continue
    }
    }
} 
return swap
}

def swap_sort(arr)
  changes = 0
  loop do
    # Find a number that is out-of-place
    _, i = arr.each_with_index.find { |val, index| val != (index + 1) }
    if i != nil
      # If such a number is found, then `j` is the position that the out-of-place number points to.
      j = arr[i] - 1

      # Swap the out-of-place number with number from position `j`.
      arr[i], arr[j] = arr[j], arr[i]

      # Increase swap counter.
      changes += 1
    else
      # If there are no out-of-place number, it means the array is sorted, and we're done.
      return changes
    end
  end
end                                                                                                

苹果Swift版本5.2.4

func minimumSwaps(arr: [Int]) -> Int {
    var swapCount = 0
    var arrayPositionValue = [(Int, Int)]()
    var visitedDictionary = [Int: Bool]()
    
    for (index, number) in arr.enumerated() {
        arrayPositionValue.append((index, number))
        visitedDictionary[index] = false
    }
    
    arrayPositionValue = arrayPositionValue.sorted{ $0.1 < $1.1 }

    for i in 0..<arr.count {
        var cycleSize = 0
        var visitedIndex = i

        while !visitedDictionary[visitedIndex]! {
            visitedDictionary[visitedIndex] = true
            visitedIndex = arrayPositionValue[visitedIndex].0
            cycleSize += 1
        }

        if cycleSize > 0 {
            swapCount += cycleSize - 1
        }
    }

    return swapCount
}

Java中使用原始类型实现整数的实现（以及测试）。

import java.util.Arrays;

public class MinSwaps {
  public static int computate(int[] unordered) {
    int size = unordered.length;
    int[] ordered = order(unordered);
    int[] realPositions = realPositions(ordered, unordered);
    boolean[] touchs = new boolean[size];
    Arrays.fill(touchs, false);
    int i;
    int landing;
    int swaps = 0;

    for(i = 0; i < size; i++) {
      if(!touchs[i]) {
        landing = realPositions[i];

        while(!touchs[landing]) {
          touchs[landing] = true;
          landing = realPositions[landing];

          if(!touchs[landing]) { swaps++; }
        }
      }
    }

    return swaps;
  }

  private static int[] realPositions(int[] ordered, int[] unordered) {
    int i;
    int[] positions = new int[unordered.length];

    for(i = 0; i < unordered.length; i++) {
      positions[i] = position(ordered, unordered[i]);
    }

    return positions;
  }

  private static int position(int[] ordered, int value) {
    int i;

    for(i = 0; i < ordered.length; i++) {
      if(ordered[i] == value) {
        return i;
      }
    }

    return -1;
  }

  private static int[] order(int[] unordered) {
    int[] ordered = unordered.clone();
    Arrays.sort(ordered);

    return ordered;
  }
}

测试

import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class MinimumSwapsSpec {
  @Test
  public void example() {
    // setup
    int[] unordered = new int[] { 40, 23, 1, 7, 52, 31 };

    // run
    int minSwaps = MinSwaps.computate(unordered);

    // verify
    assertEquals(5, minSwaps);
  }

  @Test
  public void example2() {
    // setup
    int[] unordered = new int[] { 4, 3, 2, 1 };

    // run
    int minSwaps = MinSwaps.computate(unordered);

    // verify
    assertEquals(2, minSwaps);
  }

  @Test
  public void example3() {
    // setup
    int[] unordered = new int[] {1, 5, 4, 3, 2};

    // run
    int minSwaps = MinSwaps.computate(unordered);

    // verify
    assertEquals(2, minSwaps);
  }
}

Swift 4.2：

func minimumSwaps(arr: [Int]) -> Int {
    let sortedValueIdx = arr.sorted().enumerated()
        .reduce(into: [Int: Int](), { $0[$1.element] = $1.offset })

    var checked = Array(repeating: false, count: arr.count)
    var swaps = 0

    for idx in 0 ..< arr.count {
        if checked[idx] { continue }

        var edges = 1
        var cursorIdx = idx
        while true {
            let cursorEl = arr[cursorIdx]
            let targetIdx = sortedValueIdx[cursorEl]!
            if targetIdx == idx {
                break
            } else {
                cursorIdx = targetIdx
                edges += 1
            }
            checked[targetIdx] = true
        }
        swaps += edges - 1
    }

    return swaps
}

这是一个Java的解决方案，用于解决@Archibald已经解释过的问题。

    static int minimumSwaps(int[] arr){
        int swaps = 0;
        int[] arrCopy = arr.clone();
        HashMap<Integer, Integer> originalPositionMap
                = new HashMap<>();
        for(int i = 0 ; i < arr.length ; i++){
            originalPositionMap.put(arr[i], i);
        }

        Arrays.sort(arr);
        for(int i = 0 ; i < arr.length ; i++){
            while(arr[i] != arrCopy[i]){
                //swap
                int temp = arr[i];
                arr[i] = arr[originalPositionMap.get(temp)];
                arr[originalPositionMap.get(temp)] = temp;
                swaps += 1;
            }
        }
        return swaps;
    }

在Javascript中

如果数组的计数从1开始

function minimumSwaps(arr) {
   var len = arr.length
    var visitedarr = []
    var i, start, j, swap = 0
    for (i = 0; i < len; i++) {
        if (!visitedarr[i]) {
            start = j = i
            var cycleNode = 1
            while (arr[j] != start + 1) {
                j = arr[j] - 1
                visitedarr[j] = true
                cycleNode++
            }
            swap += cycleNode - 1
        }
    }
    return swap
}

如果输入以0开头，则执行else语句

function minimumSwaps(arr) {
    var len = arr.length
    var visitedarr = []
    var i, start, j, swap = 0
    for (i = 0; i < len; i++) {
        if (!visitedarr[i]) {
            start = j = i
            var cycleNode = 1
            while (arr[j] != start) {
                j = arr[j]
                visitedarr[j] = true
                cycleNode++
            }
            swap += cycleNode - 1
        }
    }
    return swap
}

只是在扩展Darshan Puttaswamy的代码以适应当前的HackerEarth输入

Python 代码

A = [4,3,2,1]
count = 0
for i in range (len(A)):
    min_idx = i
    for j in range (i+1,len(A)):
        if A[min_idx] > A[j]:
            min_idx = j
    if min_idx > i:
        A[i],A[min_idx] = A[min_idx],A[i]
        count = count + 1
print "Swap required : %d" %count