给定整数数组 A,每次 move 操作将会选择任意 A[i]
,并将其递增 1
。
返回使A
中的每个值都是唯一的最少操作次数。
示例 1:
输入:[1,2,2]
输出:1
解释:经过一次 move 操作,数组将变为 [1, 2, 3]。
示例 2:
输入:[3,2,1,2,1,7]
输出:6
解释:经过 6 次 move 操作,数组将变为 [3, 4, 1, 2, 5, 7]。
可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。
提示:
1.0 <= A.length <= 40000
2.0 <= A[i] < 40000
该问题有几种思路,我总结了两个:
一个是我们很容易想到的,将数组先排序,然后循环遍历,将当前元素与前一位置元素进行对比,若相等则+1,同时增加一次操作数。该方法比较简单,不做过多讲解,代码如下。
另外一种方式,我们想到在构建hash散列时,为了防止hash冲突,会通过一些算法来构建索引,其中一个方法就是线性探测法
,我们能完全将这个问题变相转化为解决散列hash值冲突问题,我们来看图文说明!
我们以 [3, 2, 1, 2, 1, 7]
,来模拟一遍线性探测的过程。
step1: 插入3:
因为3的位置是空的,所以直接放入3即可
step2: 插入2:
因为2的位置是空的,所以直接放入2即可
step3: 插入1:
因为1的位置是空的,所以直接放入1即可
step4: 插入2:
此时我们发现2的位置已经有值了,于是继续向后探测,直到找到空位4,于是2映射到了4。并且!!我们要对刚刚走过的路径2->3->4进行压缩,即将他们的值都设置为本次探测到的空位4
step5: 插入1:
此时我们发现1的位置已经有值了,于是向后探测,探测到了2,发现2的位置也有值了,但是由于2在上次的过程中存了上次的空位4,所以我们直接跳转到4+1即从5开始探测就行
step6: 插入7:
因为7的位置是空的,所以直接放入7即可
/**
* @param {number[]} A
* @return {number}
*/
const pos = new Array(80000);
var minIncrementForUnique = function(A) {
pos.fill(-1); // -1表示空位
let move = 0;
// 遍历每个数字a对其寻地址得到位置b, b比a的增量就是操作数。
for (a of A) {
const b = findPos(a);
move += b - a;
}
return move;
};
function findPos(a) {
let b = pos[a];
// 如果a对应的位置pos[a]是空位,直接放入即可。
if (b == -1) {
pos[a] = a;
return a;
}
// 否则向后寻址
// 因为pos[a]中标记了上次寻址得到的空位,因此从pos[a]+1开始寻址就行了(不需要从a+1开始)。
b = findPos(b + 1);
pos[a] = b; // 寻址后的新空位要重新赋值给pos[a]哦,路径压缩就是体现在这里。
return b;
}
首先考虑 map
方法的回调函数参数含义
arr.map(function callback(currentValue[, index[, array]]) { }
•currentValue 当前遍历的值•index 当前遍历索引•array 遍历数组
然后我们分析 parseInt
参数的含义
parseInt(string, radix)
•string 被处理的值•radix 基数即进制(2、8、10、16...进制)
当遍历到1时,map回调函数的参数分别为:1、0,即parseInt(1, 0),1的十进制数 为1
当遍历到2时,map回调函数的参数分别为:2、1,即parseInt(2, 1),1进制数为2的数不存在,即为 NaN
当遍历到3时,map回调函数的参数分别为:3、2,即parseInt(3, 2),2进制数为3的数不存在,即为 NaN
[1]
945. 使数组唯一的最小增量: https://leetcode-cn.com/problems/minimum-increment-to-make-array-unique/
本文分享自 JavaScript全栈 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!