题目26:删除排序数组中的重复项 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],示例 2:
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
给定 nums = [0,0,1,1,1,2,2,3,3,4],解法1 暴力法
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
- 从前往后遍历数组，每当遇到相邻元素相同时，就把后面的所有元素向前移动一个位置，并把数组的长度减1
- 要注意边界的控制
- 此法嵌套两层循环，有可能超时
public int removeDuplicates(int[] nums) {
int n = nums.length;
for (int i = 1;
i < n;
i++) {
while (nums[i] == nums[i - 1]) {
if (i==n-1){
n--;
break;
}
for (int j = i;
j < n;
j++) {
if (j != n - 1)
nums[j] = nums[j + 1];
}
n--;
}
}
return n;
}
时间复杂度
O(n2)
空间复杂度
O(1)
解法二 游标法
- 使用两个游标i，j。i记录当前最后一个不同元素的位置，j从前往后遍历数组寻找下一个不同元素的位置，一旦找到，i++，将num[j]赋给num[i],继续遍历数组,直到遍历完.
- 此法只需要一次循环
public int removeDuplicates2(int[] nums){
int i = 0;
for (int j = 1 ;
j时间复杂度
O(n)
空间复杂度
【算法|Leetcode26删除排序数组中的重复项】O(1)
推荐阅读
- Java|Java基础——数组
- 人工智能|干货！人体姿态估计与运动预测
- java简介|Java是什么（Java能用来干什么？）
- Java|规范的打印日志
- Linux|109 个实用 shell 脚本
- 程序员|【高级Java架构师系统学习】毕业一年萌新的Java大厂面经，最新整理
- 分析COMP122 The Caesar Cipher
- Spring注解驱动第十讲--@Autowired使用
- SqlServer|sql server的UPDLOCK、HOLDLOCK试验
- jvm|【JVM】JVM08(java内存模型解析[JMM])