删除排序数组中的重复项
26. 删除排序数组中的重复项
public static int removeDuplicates(int[] nums) {
if (nums.length == 0 || nums == null) return 0;
int writeIndex = 1;
for (int i = 1;
i < nums.length;
i++) {
if (nums[i] != nums[i - 1]) nums[writeIndex++] = nums[i];
}
return writeIndex;
}
Tips:
- 不是考虑去将后面所有元素左移，而是考虑Overwrite
- 不需要担心数组的有序性，完全没有问题
- writeIndex记录的是下一个需要被覆盖的元素！
public int removeDuplicates(int[] nums) {
if (nums.length == 0 || nums == null) return 0;
int slow = 0, fast = 1;
while (fast < nums.length) {
if (nums[fast] != nums[slow]) {
nums[++slow] = nums[fast];
}
fast++;
}
// 长度为索引 + 1
return slow + 1;
}
Tips:
- 我们让慢指针 slow 走左后面，快指针 fast 走在前面探路，找到一个不重复的元素就告诉 slow 并让 slow 前进一步。这样当 fast 指针遍历完整个数组 nums 后，nums[0..slow] 就是不重复元素，之后的所有元素都是重复元素。（来自labuladong）
推荐阅读
- 数组常用方法一
- 一个选择排序算法
- Java|Java基础——数组
- 排序（归并排序）
- JS常见数组操作补充
- 【图解】9张图彻底搞懂堆排序
- JS|JS 数组求和与数组求平均值
- 超帅的js数组去重
- JavaScript|JavaScript — 初识数组、数组字面量和方法、forEach、数组的遍历
- JavaScript判断数组的方法总结与推荐