Java solution, passed all cases
static int minimumSwaps(int[] arr) { int swaps = 0; for(int i = 0; i < arr.length;){ if(arr[i] != i + 1){ swaps++; int temp = arr[arr[i] - 1]; arr[arr[i] - 1] = arr[i]; arr[i] = temp; continue; } i++; } return swaps; }
Java Solution :
int swap, count = 0; for ( int i=0; i< arr.length; i++ ) { if( arr[i] == i+1) continue; for (int j=i; j<arr.length; j++) { if(arr[j] == i+1 ) { swap = arr[i]; arr[i] = arr[j]; arr[j] = swap; count++; break; } } } return count;
I don't understand how everyone managed to solve a problem with incorrect examples from the beginning. In the example:
Example
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]
In the 1st swap, (0, 3) should not be swapped, but (0, 6) should be swapped to solve the problem correctly. It's impressive that everyone managed to solve a problem with incorrect examples from the beginning.
Python3 solution:
pos = {v: i for i, v in enumerate(arr)} swaps = 0 for i, a in enumerate(arr): if i != a - 1: correct = pos[i + 1] arr[i] = arr[correct] arr[correct] = a pos[i + 1] = i pos[a] = correct swaps += 1 return swaps
Why do I get TLE error for the following solution? Note: If I use the traditional temporary variable-based swapping then the solution works fine.
def minimumSwaps(arr): swaps = 0 idx = 0 while idx < len(arr): if arr[idx] != idx+1: arr[idx], arr[arr[idx]-1] = arr[arr[idx]-1], arr[idx] swaps += 1 else: idx += 1 return swaps
Sort 2425 Discussions, By:
Please Login in order to post a comment