minimum-swaps-to-sort-by-digit-sum.cpp (1454B)
1 int sumDigits(int input) { 2 int res = 0; 3 4 while(input > 0) { 5 res += (input % 10); 6 input /= 10; 7 } 8 return res; 9 } 10 11 std::string encodePair(std::pair<int,int> pr) { 12 return std::to_string(pr.first) + ":" + std::to_string(pr.second); 13 } 14 15 class Solution { 16 public: 17 int minSwaps(vector<int>& nums) { 18 19 std::vector<std::pair<int,int>> pairs {}; 20 std::vector<std::pair<int,int>> sortedPairs {}; 21 22 23 for(int i = 0; i < nums.size(); ++i) { 24 pairs.push_back({sumDigits(nums[i]), nums[i]}); 25 sortedPairs.push_back({sumDigits(nums[i]), nums[i]}); 26 } 27 28 std::sort(sortedPairs.begin(), sortedPairs.end()); 29 30 std::unordered_map<std::string,int> h {}; 31 32 for(int i = 0; i < pairs.size(); ++i) { 33 h[encodePair(pairs[i])] = i; 34 } 35 36 int swapCount = 0; 37 for(int i = 0; i < pairs.size(); ++i) { 38 39 if(pairs[i] != sortedPairs[i]) { 40 std::string encodedBase = encodePair(pairs[i]); 41 std::string encodedTarget = encodePair(sortedPairs[i]); 42 43 int swapIndex = h[encodedTarget]; 44 45 auto temp = pairs[i]; 46 pairs[i] = pairs[swapIndex]; 47 pairs[swapIndex] = temp; 48 49 h[encodedTarget] = i; 50 h[encodedBase] = swapIndex; 51 52 swapCount += 1; 53 } 54 } 55 56 57 return swapCount; 58 } 59 };