We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I see a lot of people confused by this one.
The trick is to not worry about the specific sorting method, you will never get the correct number of swaps with quicksort.
The second trick is to avoid reversing the SORTED list. You have to reverse the ORIGINAL data.
C++20 implementation
autocountSwaps(std::vector<int>data,boolreverseData=false){autosorted(data);sort(sorted.begin(),sorted.end());if(reverseData)reverse(data.begin(),data.end());std::unordered_map<int,int>indexArray;transform(data.begin(),data.end(),inserter(indexArray,indexArray.end()),[idx=0](intvalue)mutable{returnstd::make_pair(value,idx++);});autocounter=0;for(autoi=0;i<sorted.size();++i){autoexpected=sorted[i];// This is the value I would normally expect to find in data if it was sortedauto&original=data[i];// Reference to the original data item in position [i]if(expected==original)continue;autoexpectedPos=indexArray[expected];indexArray[original]=expectedPos;std::swap(original,data[expectedPos]);++counter;}returncounter;};intlilysHomework(std::vector<int>arr){returnstd::min(countSwaps(arr),countSwaps(arr,true));}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Lily's Homework
You are viewing a single comment's thread. Return to all comments →
I see a lot of people confused by this one. The trick is to not worry about the specific sorting method, you will never get the correct number of swaps with quicksort.
The second trick is to avoid reversing the SORTED list. You have to reverse the ORIGINAL data. C++20 implementation