seo网站模版,手机版网站如何制作软件,部门网站建设管理典型经验材料,wordpress 信息查询插件1. 题意
给定一个数组#xff0c;求最少的操作数使得数组连续。
每次操作你可选择一个数#xff0c;将它变为任意其他数。
leetcode2009
2. 题解
思路#xff1a;反向考虑#xff0c;最多能保留多少个数字使得当前数组连续。
就变成了 [ x , x s z − 1 ] [x,xsz-1]…1. 题意
给定一个数组求最少的操作数使得数组连续。
每次操作你可选择一个数将它变为任意其他数。
leetcode2009
2. 题解
思路反向考虑最多能保留多少个数字使得当前数组连续。
就变成了 [ x , x s z − 1 ] [x,xsz-1] [x,xsz−1]的滑动窗口最多包含了几个数组中的数字。
还有需要去重重复的数字一定需要一次来改变。
最后的答案即 s z − m a x _ n u m b e r _ i n _ w i n d o w sz-max\_number\_in\_window sz−max_number_in_window
其中有序数组去重对应leetcode26–删除有序数组重复项。
2.1 排序去重滑动窗口 class Solution {
public:int minOperations(vectorint nums) {sort(nums.begin(), nums.end());int sz nums.size();int cnt 0;for (int i 1; i sz; i) {if ( nums[i] ! nums[cnt]) {nums[cnt] nums[i];}}cout cnt 1 endl;int l 0;int ans 0;for (int i 1; i cnt 1; i) {if ( nums[i] - nums[l] sz - 1) {ans max(ans, i - l);while (i cnt 1 nums[i] - nums[l] sz - 1)l;}}ans max(ans, cnt 1 - l);return sz - ans;}
};2.2 排序去重二分
可以固定左边界二分寻找右边界。
class Solution {
public:int minOperations(vectorint nums) {sort(nums.begin(), nums.end());int sz nums.size();int cnt 0;for (int i 1; i sz; i) {if ( nums[i] ! nums[cnt]) {nums[cnt] nums[i];}}int l 0;int ans sz;for (int i 0; i cnt 1; i) {int l i 1;int r cnt 1;while ( l r) {int m l (r -l 1);if ( nums[m] - nums[i] sz - 1) {l m 1;}else {r m;}}ans min(ans, sz -(l - i));}return ans;}
};
