Sponsored
This approach involves sorting the array first, and then iterating through it to ensure each element is greater than the previous. By keeping track of the necessary increments for each duplicate, we can ensure that every element in the array becomes unique.
Time Complexity: O(N log N) due to sorting and O(N) for linear traversal, resulting in O(N log N) overall.
Space Complexity: O(1) since no auxiliary space is used beyond input manipulation.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5int minIncrementForUnique(std::vector<int>& nums) {
6 std::sort(nums.begin(), nums.end());
7 int moves = 0, need = nums[0];
8 for (const int& num : nums) {
9 moves += std::max(0, need - num);
10 need = std::max(need, num) + 1;
11 }
12 return moves;
13}
14
15int main() {
16 std::vector<int> nums = {3, 2, 1, 2, 1, 7};
17 std::cout << minIncrementForUnique(nums) << std::endl;
18 return 0;
19}We utilize std::sort to sort the array and then traverse it, adjusting each number to be the next available unique value. This results in a minimal number of moves needed to ensure all elements are unique.
Instead of sorting, this method uses an array to count occurrences of each integer and then processes the count. For duplicate values, increments are calculated to fill gaps until all numbers are unique.
Time Complexity: O(N + M) where M is the range of numbers, due to counting and traversal.
Space Complexity: O(M) where M is the maximum possible number in nums.
1
class Solution {
public int MinIncrementForUnique(int[] nums) {
int[] count = new int[100000];
foreach (var num in nums) count[num]++;
int moves = 0, taken = 0;
for (int i = 0; i < 100000; i++) {
if (count[i] > 1) {
taken += count[i] - 1;
moves -= i * (count[i] - 1);
} else if (taken > 0 && count[i] == 0) {
taken--;
moves += i;
}
}
return moves;
}
static void Main() {
var nums = new int[]{3, 2, 1, 2, 1, 7};
var sol = new Solution();
Console.WriteLine(sol.MinIncrementForUnique(nums));
}
}The C# solution is similar, utilizing an integer array to count occurrences. It processes this information to distribute duplicated values into open, unique slots efficiently.