建站行业,wordpress设置备份,合肥效果图公司哪家好,试用网站如何做【问题描述】
给定整数数组 A#xff0c;每次 move 操作将会选择任意 A[i]#xff0c;并将其递增 1。返回使 A 中的每个值都是唯一的最少操作次数。示例 1:输入#xff1a;[1,2,2]
输出#xff1a;1
解释#xff1a;经过一次 move 操作#xff0c;数组将变为 [1, 2, 3]。…【问题描述】
给定整数数组 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 操作是不能让数组的每个值唯一的。
提示0 A.length 40000
0 A[i] 40000
【解答思路】
1. 排序 O(NlogN)
先排序再依次遍历数组元素若当前元素小于等于它前一个元素则将其变为前一个数1。
class Solution {public int minIncrementForUnique(int[] A) {// 先排序Arrays.sort(A);int move 0;// 遍历数组若当前元素小于等于它的前一个元素则将其变为前一个数1for (int i 1; i A.length; i) {if (A[i] A[i - 1]) {int pre A[i];A[i] A[i - 1] 1;move A[i] - pre;}}return move;}}2. 注意最后一个的推导 计数排序 O(N)
class Solution {public int minIncrementForUnique(int[] A) {// counter数组统计每个数字的个数。//这里为了防止下面遍历counter的时候每次都走到40000所以设置了一个max这个数据量不设也行再额外设置min也行int[] counter new int[40001];int max -1;for (int num: A) {counter[num];max Math.max(max, num);}// 遍历counter数组若当前数字的个数cnt大于1个则只留下1个其他的cnt-1个后移int move 0;for (int num 0; num max; num) {if (counter[num] 1) {int d counter[num] - 1;move d;counter[num 1] d;}}// 最后, counter[max1]里可能会有从counter[max]后移过来的counter[max1]里只留下1个其它的d个后移。// 设 max1 x那么后面的d个数就是[x1,x2,x3,...,xd],// 因此操作次数是[1,2,3,...,d],用求和公式求和。int d counter[max 1] - 1;move (1 d) * d / 2;return move;}
}3. 线性探测法含路径压缩 O(N) 神仙解法
把原数组映射到一个地址不冲突的区域 和解决hash冲突的线性探测法比较相似直接线性探测可能会由于冲突导致反复探测耗时太长 - 考虑探测的过程中进行路径压缩经过某条路径最终探测到一个空位置x后将这条路径上的值都变成空位置所在的下标x那么假如下次探测的点又是这条路径上的点则可以直接跳转到这次探测到的空位置x从x开始继续探测。
下面用样例2[3, 2, 1, 2, 1, 7]来模拟一遍线性探测的过程。
模拟的过程中用int move来记录操作数即要求的增量数。
step1: 插入3 因为3的位置是空的所以直接放入3即可。此时数组变成了上图红色表示本次的更改
move 0 保持不变;
step2: 插入2 因为2的位置是空的所以直接放入2即可。此时数组变成了上图红色表示本次的更改
move 0 保持不变;
step3: 插入1 因为1的位置是空的所以直接放入1即可。此时数组变成了上图红色表示本次的更改
move 0 保持不变;
step4: 插入2 此时我们发现2的位置已经有值了于是继续向后探测直到找到空位4于是2映射到了4。
⚠️并且我们要对刚刚走过的路径2-3-4进行压缩即将他们的值都设置为本次探测到的空位4(那么下次探测就可以直接从4往后找了)。
此时数组变成了上图红色表示本次的更改
move move 4 - 2 2;
step5: 插入1 此时我们发现1的位置已经有值了于是向后探测探测到了2发现2的位置也有值了但是由于2在上次的过程中存了上次的空位4所以我们直接跳转到41即从5开始探测就行了而不需要重复走一遍2-3-4这条路径喽此时我们发现5是个空位因此将1映射到5并且对刚刚走过的路径1-2-5进行路径压缩 即 使其都映射到5
此时数组变成了上图红色表示本次的更改
move move 5 - 1 6;
step6: 插入7 因为7的位置是空的所以直接放入7即可。此时数组变成了上图红色表示本次的更改
move 6 保持不变;
以上最终move为6。
class Solution {int[] pos new int [80000];public int minIncrementForUnique(int[] A) {Arrays.fill(pos, -1); // -1表示空位int move 0;// 遍历每个数字a对其寻地址得到位置b, b比a的增量就是操作数。for (int a: A) {int b findPos(a); move b - a;}return move;}// 线性探测寻址含路径压缩private int findPos(int a) {int b pos[a];// 如果a对应的位置pos[a]是空位直接放入即可。if (b -1) { pos[a] a;return a;}// 否则向后寻址// 因为pos[a]中标记了上次寻址得到的空位因此从pos[a]1开始寻址就行了不需要从a1开始。b findPos(b 1); //递归pos[a] b; // ⚠️寻址后的新空位要重新赋值给pos[a]哦路径压缩就是体现在这里。return b;}
}4. 贪心算法 时间复杂度O(Nlog N) 空间复杂度O(1) public int minIncrementForUnique(int[] A) {int len A.length;if (len 0) {return 0;}Arrays.sort(A);// 打开调试// System.out.println(Arrays.toString(A));int preNum A[0];int res 0;for (int i 1; i len; i) {// preNum 1 表示当前数「最好」是这个值if (A[i] preNum 1) {preNum A[i];} else if (A[i] preNum 1) {// 当前这个数已经足够大这种情况可以合并到上一个分支preNum A[i];} else {// A[i] preNum 1res (preNum 1 - A[i]);preNum;}}return res;}
【总结】
思维过于局限 统计相同的数字分别1使用两层循环导致超时。思维不跳跃没有整体把握第二种方法和第三种方法看了半天。
转载来自 https://leetcode-cn.com/problems/minimum-increment-to-make-array-unique/solution/ji-shu-onxian-xing-tan-ce-fa-onpai-xu-onlogn-yi-ya/
