GRAYRHINO's blog

By GRAYRHINO, history, 4 years ago, In English

Given an array of integers (duplicates are possible), find the minimum number of swaps to sort the array. For [3,9,2,4,2] it should be 2 : [3, 9, 2, 4, 2] -> [2, 9, 3, 4, 2] -> [2, 2, 3, 4, 9]

If the elements are distinct then there's a time complexity O(nlog(n)) and space complexity O(n) solution here. However, I couldn't find any satisfactory proof for solutions where array contains duplicates. So, I have two questions:

  1. What is the most optimal solution when all the elements are distinct?
  2. Any algorithm when the array contains duplicates?

This seems to be very common questions in top tech interviews. Your ideas and suggestions (possibly code) would be much appreciated.

Full text and comments »

  • Vote: I like it
  • +91
  • Vote: I do not like it