LeetCode Remove Duplicates from Sorted Array
Problem
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example, Given input array nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.
题目其实包含两部分要求。首先，需要返回一个已排序数组，值不相同的元素的个数。例如：[1,1,2]返回2。这也是题目代码可以自动校验的部分。另一个隐含的要求是，要求不使用新的空间，并且在算出个数n后，将值不相同的元素，依次放置到数组的前N位。
Java 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
package com.coderli.leetcode.algorithms.easy;
/**
* Given a sorted array, remove the duplicates in place such that each element appear only once and
* return the new length.
* <p>
* Do not allocate extra space for another array, you must do this in place with constant memory.
* <p>
* For example,
* Given input array nums = [1,1,2],
* <p>
* Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
* It doesn't matter what you leave beyond the new length.
*
* @author li.hzh 2017-10-22 21:24
*/
public class RemoveDuplicatesFromSortedArray {
public static void main(String[] args) {
RemoveDuplicatesFromSortedArray rdfSortedArray = new RemoveDuplicatesFromSortedArray();
System.out.println(rdfSortedArray.removeDuplicates(new int[]{1}));
System.out.println(rdfSortedArray.removeDuplicates(new int[]{1, 1}));
System.out.println(rdfSortedArray.removeDuplicates(new int[]{1, 1, 2}));
System.out.println(rdfSortedArray.removeDuplicates(new int[]{1, 1, 2, 2}));
System.out.println(rdfSortedArray.removeDuplicates(new int[]{1, 1, 1, 2, 2}));
System.out.println(rdfSortedArray.removeDuplicates(new int[]{1, 1, 2, 2, 3, 3}));
System.out.println(rdfSortedArray.removeDuplicates(new int[]{1, 2, 2, 3, 4, 4}));
}
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int compareValue = nums[0];
int result = 1;
for (int i = 1; i < nums.length; i++) {
if (compareValue < nums[i]){
compareValue = nums[i];
nums[result] = compareValue;
result++;
}
}
return result;
}
}
分析
解法很简单，一次遍历。用变量compareValue记录当前比较的值，result为不相同的元素个数。当需要比较的值与当前元素值不相同时，即有新值出现的时候，结果+1，将新值放置到当前不相同元素个数所在的索引位即可。（因为题目不要求，除了不相同的元素之外的元素分配。）
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
"luogu-"系列题目可在洛谷题库进行在线评测。
"bcqm-"系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
