前言#
今天有两道题，其中一道是另一道的变体，所以放到一起
题目1#
给你一个 非严格递增排列 的数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
- 更改数组
nums，使nums的前k个元素包含唯一元素，并按照它们最初在nums中出现的顺序排列。nums的其余元素与nums的大小不重要。 - 返回
k。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}如果所有断言都通过，那么您的题解将被 通过。
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。提示：
1 <= nums.length <= 3 * 104-104 <= nums[i] <= 104nums已按 非严格递增 排列
分析#
这里拿到的数组已经是递增排序了的，所以我们可以直接nums[i] == nums[i - 1]来判断是否是相等的，如果是，那就是重复的元素，直接移除即可。
解#
pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
let len = nums.len();
if len <= 0 {
return 0
}
// count在这里不是用来计算非重复个数的，而是用来计算当前移除的个数，保证下标位置的正确
let mut count = 0;
// 由于第一个一定是非重复的，所以就没必要从0开始
let mut i = 1;
let mut last_one = nums[0];
while i < len {
if nums[i - count] == last_one {
count += 1;
i += 1;
nums.remove(i - count);
} else {
last_one = nums[i - count];
i += 1;
}
}
// dbg!(&nums);
nums.len() as i32
}没啥好说的，另外这里应该不用移除元素，题目只需要我们将新的长度返回即可，所以可以使用最初的len - count
测试用例#
#[cfg(test)]
mod tests {
use super::{ remove_duplicates, remove_duplicates2 };
#[test]
fn test_remove_duplicates () {
assert_eq!(remove_duplicates(&mut [1,1,2].to_vec()), 2);
assert_eq!(remove_duplicates(&mut [0,0,1,1,1,2,2,3,3,4].to_vec()), 5);
}
}然后我们来看下变体
题目2#
在上面的基础下：
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
分析#
需要我们使用O(1)的空间复杂度，也就是不能使用一维以上的结构。
这个简单，我们再搞个变量用来表示重复次数即可。
解#
pub fn remove_duplicates2(nums: &mut Vec<i32>) -> i32 {
let len = nums.len();
if len <= 0 {
return 0
}
// count在这里不是用来计算非重复个数的，而是用来计算当前移除的个数，保证下标位置的正确
let mut count = 0;
// 由于第一个一定是非重复的，所以就没必要从0开始
let mut i = 1;
let mut last_one = nums[0];
// 由于第一个元素已经站位1个，所以初始值是1
let mut last_one_dp_count = 1;
while i < len {
if nums[i - count] == last_one {
i += 1;
last_one_dp_count += 1;
if last_one_dp_count > 2 {
count += 1;
nums.remove(i - count);
}
} else {
last_one = nums[i - count];
i += 1;
// 初始化
last_one_dp_count = 1;
}
}
// dbg!(&nums);
nums.len() as i32
}没啥好说的
测试用例#
#[cfg(test)]
mod tests {
use super::{ remove_duplicates, remove_duplicates2 };
#[test]
fn test_remove_duplicates () {
assert_eq!(remove_duplicates(&mut [1,1,2].to_vec()), 2);
assert_eq!(remove_duplicates(&mut [0,0,1,1,1,2,2,3,3,4].to_vec()), 5);
}
#[test]
fn test_remove_duplicates2 () {
assert_eq!(remove_duplicates2(&mut [1,1,1,2,2,3].to_vec()), 5);
assert_eq!(remove_duplicates2(&mut [0,0,1,1,1,1,2,3,3].to_vec()), 7);
}
}总结#
这题没啥好说的，主要是给的数组已经是排序了的，如果没有排序，那么我们的空间复杂度要到O(n)，因为相同元素不连续，所以我们还得记录元素出现的个数。