Untitled
public int countMinSwapsToSort(List<Integer> vec) { int swaps = 0; List<Integer> sortedVec = new ArrayList<>(vec); Collections.sort(sortedVec); Map<Integer, Integer> mp = new HashMap<>(); // nums[i] -> i for (int i = 0; i < vec.size(); i++) { mp.put(vec.get(i), i); } for (int i = 0; i < vec.size(); i++) { if (vec.get(i).equals(sortedVec.get(i))) { continue; // no swap required } int currIdx = mp.get(sortedVec.get(i)); mp.put(vec.get(i), currIdx); mp.put(vec.get(currIdx), i); Collections.swap(vec, currIdx, i); swaps++; } return swaps; }
Leave a Comment