网站制作软件都是什么,阿里云服务器安装wordpress,个人网站备案名字不同,网站建设mfdos 优帮云文章目录 题目思路代码复杂度分析时间复杂度空间复杂度 结果总结 题目
题目链接#x1f517; 给你一个整数数组 n u m s nums nums 。每一次操作中#xff0c;你可以将 n u m s nums nums 中 任意 一个元素替换成 任意 整数。
如果 n u m s nums nums 满足以下条件… 文章目录 题目思路代码复杂度分析时间复杂度空间复杂度 结果总结 题目
题目链接 给你一个整数数组 n u m s nums nums 。每一次操作中你可以将 n u m s nums nums 中 任意 一个元素替换成 任意 整数。
如果 n u m s nums nums 满足以下条件那么它是 连续的 n u m s nums nums 中所有元素都是 互不相同 的。 n u m s nums nums 中 最大 元素与 最小 元素的差等于 n u m s . l e n g t h − 1 nums.length - 1 nums.length−1 。 比方说 n u m s [ 4 , 2 , 5 , 3 ] nums [4, 2, 5, 3] nums[4,2,5,3] 是 连续的 但是 n u m s [ 1 , 2 , 3 , 5 , 6 ] nums [1, 2, 3, 5, 6] 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 ≤ n u m s . l e n g t h ≤ 1 0 5 1 \leq nums.length \leq 10^5 1≤nums.length≤105 1 ≤ n u m s [ i ] ≤ 1 0 9 1 \leq nums[i] \leq 10^9 1≤nums[i]≤109 思路
对数组进行排序这样相邻的元素就可以保证是连续的。然后去除重复元素确保数组中的元素互不相同。对于数组中的每个元素 n u m s [ i ] nums[i] nums[i]我们需要找到满足条件的最大元素 n u m s [ j ] nums[j] nums[j]使得 n u m s [ j ] − n u m s [ i ] n u m s . s i z e ( ) − 1 nums[j] - nums[i] nums.size() - 1 nums[j]−nums[i]nums.size()−1。使用二分查找来寻找满足条件的最大元素。具体地可以遍历数组中的每个元素 n u m s [ i ] nums[i] nums[i]然后使用二分查找找到最大值不超过 n u m s [ i ] n u m s . s i z e ( ) − 1 nums[i] nums.size() - 1 nums[i]nums.size()−1 的元素即 n u m s [ j ] ≤ n u m s [ i ] n u m s . s i z e ( ) − 1 nums[j] \leq nums[i] nums.size() - 1 nums[j]≤nums[i]nums.size()−1。对于每个元素 n u m s [ i ] nums[i] nums[i]可以计算需要的操作次数为 n u m s . s i z e ( ) − ( j − i 1 ) nums.size() - (j - i 1) nums.size()−(j−i1)其中 j j j 是满足条件的最大元素的下标。
代码
class Solution {
public:int minOperations(vectorint nums) {ranges::sort(nums);int n nums.size();nums.resize(unique(nums.begin(), nums.end()) - nums.begin());int m nums.size();int res INT_MAX;for(int i 0; i m; i) {int x nums[i];int y x n - 1;int l i, r m - 1;while(l r) {int mid (l r 1) / 2;if(nums[mid] y) r mid - 1;else l mid;}res min(res, n - (l - i 1));} return res;}
};复杂度分析
时间复杂度 O ( n log n ) O(n \log n) O(nlogn)
空间复杂度 O ( 1 ) O(1) O(1)
结果 总结
关键在于如何通过排序和遍历找到满足条件的最小操作次数。我们通过排序数组并去除重复元素然后对每个元素进行遍历通过二分查找找到最大值不超过 y y y 的元素并计算需要的操作次数最后选择操作次数最小的那个作为结果。
