做现货值得关注的财经网站,泰安网络优化,网站建设做账,手机 写wordpress2024.4.8 题目来源我的题解方法一 去重排序滑动窗口 题目来源
力扣每日一题#xff1b;题序#xff1a;2009
我的题解
方法一 去重排序滑动窗口 参考官方题解。 记数组 nums的长度为 n。经过若干次操作后#xff0c;若数组变为连续的#xff0c;那么数组的长度不会改变排序滑动窗口 题目来源
力扣每日一题题序2009
我的题解
方法一 去重排序滑动窗口 参考官方题解。 记数组 nums的长度为 n。经过若干次操作后若数组变为连续的那么数组的长度不会改变仍然为 n且数组最大值与最小值之差为 n−1所有元素均不相同。可以反向考虑假设最后连续的数组的最小值为 left则最大值 rightleftn−1。原数组 nums 中如果有位于 [left,right]中的如果只出现一次可以对其进行保留多次出现时则需要对其进行操作不在这个区间的数字也需要对其进行操作将它们变成其他数字来对这个区间进行补足。因此需要统计原数组 nums中位于区间 [left,right]内不同的数字个数 k而 n−k 就是需要进行的操作数。 接下来就是需要确定 left可以将原数组 nums 所有不同的数字作为 left的候选值分别计算出 n−k然后求出最小值。这样的话可以先将原数字进行去重后排序然后利用滑动窗口。滑动窗口左端点的值作为 left然后向右扩展右端点窗口的长度即为 k求出所有可能性下最小的 n−k 即可。 时间复杂度O(n×logn)其中 n 是数组 nums 的长度。排序消耗 O(n×logn)滑动窗口消耗 O(n)。 空间复杂度O(n) public int minOperations(int[] nums) {SetInteger setnew HashSet();int nnums.length;for(int i0;in;i){set.add(nums[i]);}ListInteger listnew ArrayList(set);list.sort((a,b)-a-b);int count0;int resn;for(int i0;ilist.size();i){int leftlist.get(i);int rightleftn-1;//移动窗口while(countlist.size()list.get(count)right){resMath.min(res,n-(count-i1));count;}}return res;
}有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
