class Solution {
public:
int minOperations(vector<int>& nums) {
}
};
2009. 使数组连续的最少操作数
给你一个整数数组 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 <= 1051 <= nums[i] <= 109原站题解
javascript 解法, 执行用时: 236 ms, 内存消耗: 62.9 MB, 提交时间: 2024-04-08 09:20:01
/**
* @param {number[]} nums
* @return {number}
*/
var minOperations = function(nums) {
const n = nums.length;
nums.sort((a, b) => a - b);
let j = 1;
for (let i = 1; i < n; i++) {
if (nums[i] !== nums[i - 1]) {
nums[j++] = nums[i]; // 原地去重
}
}
let ans = 0, left = 0;
for (let i = 0; i < j; i++) {
while (nums[left] < nums[i] - n + 1) { // nums[left] 不在窗口内
left++;
}
ans = Math.max(ans, i - left + 1);
}
return n - ans;
};
rust 解法, 执行用时: 32 ms, 内存消耗: 4.1 MB, 提交时间: 2023-09-14 01:03:08
impl Solution {
pub fn min_operations(mut nums: Vec<i32>) -> i32 {
nums.sort();
let length=nums.len();
let mut unique_nums=vec![];
let mut prev=i32::MAX;
for i in nums{
if i==prev{
continue;
}else{
prev=i;
}
unique_nums.push(i);
}
let mut left=0;
let mut right=1;
let mut max=0;
while right<unique_nums.len(){
if unique_nums[right]-unique_nums[left]>length as i32-1{
left+=1;
}else{
max=max.max(right-left);
right+=1;
}
}
length as i32-max as i32-1
}
}
python3 解法, 执行用时: 152 ms, 内存消耗: 33.3 MB, 提交时间: 2023-09-14 01:02:30
class Solution:
def minOperations(self, nums: List[int]) -> int:
n = len(nums)
a = sorted(set(nums))
m, left = len(a), 0
for i in range(m):
if a[i] - a[left] >= n: left += 1
return n - (m - left)
python3 解法, 执行用时: 260 ms, 内存消耗: 33.3 MB, 提交时间: 2023-09-14 01:02:16
class Solution:
def minOperations(self, nums: List[int]) -> int:
n = len(nums)
a = list(set(nums))
a.sort()
an = len(a)
cur = 0
r = 0
for l in range(an):
while r + 1 < an and a[r + 1] - a[l] <= n - 1:
r += 1
cur = max(cur, r - l + 1)
return n - cur
java 解法, 执行用时: 47 ms, 内存消耗: 56.6 MB, 提交时间: 2023-09-14 01:01:55
class Solution {
public int minOperations(int[] nums) {
if (nums.length == 1)
return 0;
int n = nums.length;
Arrays.sort(nums);
int k = 0;
for (int i = 1; i < nums.length; i++){
if (nums[k] != nums[i]){
nums[++k] = nums[i];
}
}
int ans = 0;
for (int i = 1; i <= k; i++){
int l = 0;
int r = i;
while (l < r){
int mid = l + r >> 1;
if (nums[mid] < nums[i] - n + 1){
l = mid+1;
}else{
r = mid;
}
}
ans = Math.max(ans,i - r + 1);
}
return n - ans;
}
}
cpp 解法, 执行用时: 188 ms, 内存消耗: 63 MB, 提交时间: 2023-09-14 01:01:41
class Solution {
public:
int minOperations(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
int ans = 0;
for (int i = 0; i < nums.size(); ++ i)
{
int l = 0, r = i;
int mid;
while (l < r) // 找到满足要求最小的 l
{
mid = l + r >> 1;
if (nums[mid] >= nums[i] - n + 1) r = mid;
else l = mid + 1;
}
ans = max(ans, i - r + 1);
}
return n - ans;
}
};
golang 解法, 执行用时: 200 ms, 内存消耗: 9.8 MB, 提交时间: 2023-09-14 01:01:15
func minOperations(nums []int) (ans int) {
n := len(nums)
sort.Ints(nums)
nums = unique(nums)
for r, v := range nums {
l := sort.SearchInts(nums[:r], v-n+1)
ans = max(ans, r-l+1) // [l,r] 内的元素均可以保留
}
return n - ans
}
// 原地去重
func unique(a []int) []int {
k := 0
for _, v := range a[1:] {
if a[k] != v {
k++
a[k] = v
}
}
return a[:k+1]
}
func max(a, b int) int {
if b > a {
return b
}
return a
}