[HackerRank] Preparation_Kit (08. Minimum Swaps 2) [Array]

You are given an unordered array consisting of consecutive integers ∈ [1, 2, 3, ..., n] without any duplicates. You are allowed to swap any two elements. Find the minimum number of swaps required to sort the array in ascending order.

Example

arr = [7, 1, 3, 2, 4, 5, 6]

Perform the following steps:

i   arr                         swap (indices)
0   [7, 1, 3, 2, 4, 5, 6]   swap (0,3)
1   [2, 1, 3, 7, 4, 5, 6]   swap (0,1)
2   [1, 2, 3, 7, 4, 5, 6]   swap (3,4)
3   [1, 2, 3, 4, 7, 5, 6]   swap (4,5)
4   [1, 2, 3, 4, 5, 7, 6]   swap (5,6)
5   [1, 2, 3, 4, 5, 6, 7]

It took 5 swaps to sort the array.

Function Description

Complete the function minimumSwaps in the editor below.

minimumSwaps has the following parameter(s):

• int arr[n]: an unordered array of integers

Returns

• int: the minimum number of swaps to sort the array

Input Format

The first line contains an integer, n, the size of arr.
The second line contains n space-separated integers arr[i].

Constraints

• 1 <= n <= 10^5
• 1 <= arr[i] <=n

 

func minimumSwaps(arr: [Int]) -> Int {
    var a: [Int] = arr
    var ans = 0
    var i = 0
    while i < a.count {
        let originPos = a[i] - 1
        if (i != originPos) { // two of values -> i == originPos
             let tmp = a[originPos]//willBeMoved
            a[originPos] = a[i]
            a[i] = tmp
            ans += 1
         } else {
             i += 1
         }
    }
    return ans
}

1. 하나씩 제자리로 돌려보내기// 데려오는 애(누군지 모름), 아는 애를 보내기

2. 양쪽 다 제자리 찾을 때까지는 다음 단계로 넘어가지 X

 

---

https://www.hackerrank.com/challenges/minimum-swaps-2/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays