1. Description
Reorder nums, an array of distinct positive integers, by ascending digit sum. When digit sums match, place the smaller integer first.
Each operation exchanges the values at any two different indices. Return the fewest operations needed to reach the required order.
2. Example
Example 1
Input: nums = [37,100]
Output: 1
Explanation: The digit sums are 10 and 1. Exchange the two elements to obtain [100,37].
Example 2
Input: nums = [22,14,33,7]
Output: 0
Explanation: The digit sums are [4,5,6,7], so no swaps are necessary.
Example 3
Input: nums = [18,43,34,16]
Output: 2
Explanation: The target order is [16,34,43,18]. Exchange 18 with 16 and 43 with 34; equal digit sums are ordered by numeric value.
3. Constraints
- 1 <= nums.length <= 10$^5$
- 1 <= nums[i] <= 10$^9$
- All elements of nums are distinct.
4. Solutions
Sorting with Cycle Decomposition
n = nums.size()
Time complexity: O(n log n)
Space complexity: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| // Sort by digit sum and value while retaining each element's original index.
// Decompose the index permutation into cycles; a cycle of length m needs m - 1 swaps.
class Solution {
public:
int minSwaps(const vector<int> &nums) {
const int n = nums.size();
struct Element {
int digit_sum;
int value;
int original_index;
};
vector<Element> sorted_elements;
sorted_elements.reserve(n);
for (int i = 0; i < n; ++i) {
sorted_elements.push_back({get_digit_sum(nums[i]), nums[i], i});
}
sort(
sorted_elements.begin(), sorted_elements.end(), [](const Element &a, const Element &b) {
return a.digit_sum < b.digit_sum || a.digit_sum == b.digit_sum && a.value < b.value;
});
vector<bool> visited(n, false);
int swap_count = 0;
for (int start_index = 0; start_index < n; ++start_index) {
if (visited[start_index]) {
continue;
}
int current_index = start_index;
int cycle_length = 0;
while (!visited[current_index]) {
visited[current_index] = true;
++cycle_length;
current_index = sorted_elements[current_index].original_index;
}
swap_count += cycle_length - 1;
}
return swap_count;
}
private:
static int get_digit_sum(int num) {
int digit_sum = 0;
while (num > 0) {
digit_sum += num % 10;
num /= 10;
}
return digit_sum;
}
};
|