leetcode:那些年我遇到过的编程题008:使数组唯一的最小增量
程序员文章站
2022-06-10 19:19:37
...
leetcode:那些年我遇到过的编程题008:使数组唯一的最小增量
首先我们要理清我们的思路,最终目的是让数组中每一个值都是互不相等的,那么我们首先要弄清楚如何判断一个数组中的是不是每个值都不相同,这里我选择用hashset来判断。
解法:
class Solution {
public int minIncrementForUnique(int[] A) {
int moveNum = 0;
Set<Integer> list = new HashSet<>();
for(int i =0;i<A.length;i++){
if(!list.contains(A[i])){
list.add(A[i]);
}
else{
A[i]++;
moveNum++;
}
i--;
}
return moveNum;
}
}
我真想把我现在的表情打在屏幕上,这就一个for循环怎么就超时了…????了。突然一想,别人要的是最少次数,我好像把这个忘了…
解法一:贪心算法,思路是先把A按从小到大排好序,然后挨个把A[i]和A[i-1]相比较,如果小于等于后者,则把A[i]进行move操作,统计次数。
class Solution {
public int minIncrementForUnique(int[] A) {
int moveNum = 0;
Arrays.sort(A);
for(int i =1;i<A.length;i++){
if(A[i]<=A[i-1]){
A[i]++;
i--;
moveNum++;
}
}
return moveNum;
}
}