55 lines
2.1 KiB
Markdown
55 lines
2.1 KiB
Markdown
---
|
||
id: "20220303"
|
||
date: "2022/03/03 10:38:05"
|
||
title: "leetcode.Q26.删除有序数组中的重复项"
|
||
tags: ["java", "leetcode", "array"]
|
||
categories:
|
||
|
||
- "算法"
|
||
- "leetcode刷题"
|
||
|
||
---
|
||
|
||
## 解析思路
|
||
|
||
leetcode 简单，题目描述[点击这里](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/)。
|
||
|
||
本题属于简单的数组操作题.看完题目大部分人首先想到的解法肯定是删除重复的元素，直到得出结果，但这并不是最优解，显而易见删除元素将重复元素从数组中排除，然后将后面 的元素移动到前面来，效率较低。
|
||
|
||
<!-- more -->
|
||
|
||
其实我们可以换一种思路，删除重复项也可以理解为将不重复的项找出来，由于这是一个有序数组，那么很容易判断一个数是否为不重复的项：如果`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]中（最后一个数肯定要加入结果中，因为我们是通过比较当前数和下一个数是否相等来决定要不要加入，最后一个数是无法比较的）
|
||
|
||
## 代码
|
||
|
||
```java
|
||
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}));
|
||
}
|
||
}
|
||
|
||
``` |