Every day a leetcode
题目来源:945. 使数组唯一的最小增量
解法1:hash计数
用一个hash表统计nums中各数字出现的次数。
设置count统计+1的次数。
遍历hash表,若hash[i]>1,说明有重复个数字,根据贪心的思想,应该将hash[i]-1个该值+1,则有:
count+=hash[i]-1;
hash[i+1]+=hash[i]-1;
hash[i]=1;
结果:
无论是int,还是long long,都溢出了。
解法2:快排+贪心
先将nums数组从小到大排序,依次对比相邻的两个数,若后一个数小于等于前一个数,说明要对后一个数做+1操作。
根据贪心的思想,只需要让后一个数比前一个数大1,就能让+1次数最少。
故+1次数为nums[i-1]-nums[i]+1,同时将nums[i修改为nums[i-1]+1。
代码:
void swap(int* a,int low,int high){
int c=a[low];
a[low]=a[high];
a[high]=c;
return;
}
int partition(int* a,int low,int high){
int pivotkey;
int middle=(low+high)/2;
if(a[low]>a[high]){
swap(a,low,high);
}
if(a[middle]>a[high]){
swap(a,middle,high);
}
if(a[middle]>a[low]){
swap(a,low,middle);
}
pivotkey=a[low];
while(low<high){
while(low<high&&a[high]>=pivotkey){
high--;
}
a[low]=a[high];
while(low<high&&a[low]<=pivotkey){
low++;
}
a[high]=a[low];
}
a[low]=pivotkey;
return low;
}
void quicksort(int* a,int low,int high){
int pivot;
while(low<high){
pivot=partition(a,low,high);
quicksort(a,low,pivot-1);
low=pivot+1;
}
return;
}
int minIncrementForUnique(int* nums, int numsSize){
int ans=0;
quicksort(nums,0,numsSize-1);
for(int i=1;i<numsSize;i++)
{
if(nums[i]<=nums[i-1])
{
ans+=nums[i-1]-nums[i]+1;
nums[i]=nums[i-1]+1;
}
}
return ans;
}
结果: