国家建设官方网站,旅行社做网站,网站外链分析工具,阿里云搭建网站教程使数组连续的最少操作数
给你一个整数数组 nums 。每一次操作中#xff0c;你可以将 nums 中 任意 一个元素替换成 任意 整数。
如果 nums 满足以下条件#xff0c;那么它是 连续的 #xff1a;
nums 中所有元素都是 互不相同 的。 nums 中 最大 元素与 最小 元素的差等于…使数组连续的最少操作数
给你一个整数数组 nums 。每一次操作中你可以将 nums 中 任意 一个元素替换成 任意 整数。
如果 nums 满足以下条件那么它是 连续的
nums 中所有元素都是 互不相同 的。 nums 中 最大 元素与 最小 元素的差等于 nums.length - 1 。 比方说nums [4, 2, 5, 3] 是 连续的 但是 nums [1, 2, 3, 5, 6] 不是连续的 。
请你返回使 nums 连续 的 最少 操作次数。
示例 1
输入nums [4,2,5,3] 输出0 解释nums 已经是连续的了。 示例 2
输入nums [1,2,3,5,6] 输出1 解释一个可能的解是将最后一个元素变为 4 。 结果数组为 [1,2,3,5,4] 是连续数组。 示例 3
输入nums [1,10,100,1000] 输出3 解释一个可能的解是
将第二个元素变为 2 。将第三个元素变为 3 。将第四个元素变为 4 。 结果数组为 [1,2,3,4] 是连续数组。
提示
1 nums.length 1 0 5 10^5 105 1 nums[i] 1 0 9 10^9 109
思路
一开始没想到去重分享下思路吧。 先对数组排序利用滑动窗口的思想对每一个数cur若以该数为目标数组的首位则小于等于curlen-1的数都是不需要修改的 因此向后找到第一个大于curlen-1的数 索引为j该位置到末尾的距离len-j加上i之前的距离就是当前情况下需要修改的元素个数。 当然这里向后找的过程由于数组是递增的可以二分。 这样提交了之后发现有重复元素挂了。[8,5,9,9,8,4] 很显然排序后为[4,5,8,8,9,9]用刚才的思路发现以4开头则所有的元素都 小于等于9则修改次数为0。考虑到重复元素是肯定需要修改的无论是否在该范围内因此可以对数组进行预处理先讲所有重复元素 处理为最小值然后再向后找的过程中为了防止多个连续最小值多加个判断。
class Solution {public int minOperations(int[] nums) {int res Integer.MAX_VALUE;int len nums.length;// 去重SetInteger s new HashSet();for(int i 0; i len; i) {if(!s.add(nums[i]))nums[i] Integer.MIN_VALUE;}Arrays.sort(nums);for(int i 0; i len; i) {if(i res) break; // 剪枝int j i 1; // i到j之外的数是当前需要修改的int cur nums[i];while(j len nums[j] ! Integer.MIN_VALUE nums[j] cur len - 1)j;res Math.min(res, len - j i);}return res;}
}
