Leetcode945. 使数组唯一的最小增量

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;

结果:
Leetcode945. 使数组唯一的最小增量
无论是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;
}

结果:
Leetcode945. 使数组唯一的最小增量

上一篇:【Java集合】HashMap的get()源码详解以及JDK1.7与JDK1.8的区别


下一篇:索引设计 《数据库高效优化》 p300