leetcode.Q26.删除有序数组中的重复项

解析思路

leetcode 简单,题目描述点击这里

本题属于简单的数组操作题.看完题目大部分人首先想到的解法肯定是删除重复的元素,直到得出结果,但这并不是最优解,显而易见删除元素将重复元素从数组中排除,然后将后面 的元素移动到前面来,效率较低。

其实我们可以换一种思路,删除重复项也可以理解为将不重复的项找出来,由于这是一个有序数组,那么很容易判断一个数是否为不重复的项:如果nums[i]!=nums[i+1],那么nums[i]就一定是一个不重复的项,
可将其加入到结果集中。同时使用一个变量来记录结果数。整理一下思路如下:

  1. 定义count=0,记录已找到的不重复数字
  2. 从i=0开始遍历到i=nums.length-2,判断nums[i]==nums[i+1]
  3. 如果相等,nums[count]=nums[i],count++
  4. 不等继续第二步
  5. 最后将数组最后一个数放到nums[count]中(最后一个数肯定要加入结果中,因为我们是通过比较当前数和下一个数是否相等来决定要不要加入,最后一个数是无法比较的)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Q26 {
public int removeDuplicates(int[] nums) {
int n = nums.length;
//不重复元素的个数
int count = 0;
//最后一个元素单独处理
//找到一个重复序列的最后一个元素
for (int i = 0; i < n - 1; i++) {
if (nums[i] != nums[i + 1]) {
nums[count++] = nums[i];
}
}
//由于是当前元素和下一个元素作比较,那么最后一个元素一定是目标元素
nums[count++] = nums[n - 1];
return count;
}

public static void main(String[] args) {
System.out.println(new Q26().removeDuplicates(new int[]{0, 0, 1, 1, 1, 2, 2, 3, 3, 4}));
}
}

本文原创发布于:https://blog.fleyx.com,转载请注明出处

如果本篇文章对您有帮助欢迎打赏哦!
微信打赏 支付宝打赏
关注公众号(烦嚣的人)
微信公众号