面试题求解：remove first duplicate number from an array - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

面试题求解：remove first duplicate number from an array

面试题求解：remove first duplicate number from an array# JobHunting - 待字闺中

i*h2014-12-12 08:12

1 楼

LC只刷了60题，今天面试碰到个题（不知道lc里有没有，粗略扫了一遍题目名字没看到
），求思路。
题目：一个array里有一组或以上重复的数字（可能只有一组，可能有几组），需要
remove第一次出现的重复的数字，然后顺序要保持和原来一样。
比如：
｛1，5，2，3，5，4，5，6｝－> {1，2，3，5，4，5，6｝
｛1，5，2，3，2，5，4，5，6｝－>{1，3，2，5，4，5，6｝
求思路求解，谢谢了！
我能想到的就只有用hashmap.

O*D2014-12-12 08:12

2 楼

第二个例子为什么5和2都去了？

z*b2014-12-12 08:12

3 楼

时间空间复杂度有啥要求吗？

i*h2014-12-12 08:12

4 楼

第二个例子是表示5和2都有重复，所以第一次出现的重复数字需要删除。

【在 O***D 的大作中提到】

: 第二个例子为什么5和2都去了？

i*h2014-12-12 08:12

5 楼

最优能写成什么样？我想不到，所以想求大牛解答。

【在 z***b 的大作中提到】

: 时间空间复杂度有啥要求吗？

z*e2014-12-12 08:12

6 楼

可能不算最优，扫两遍
int len = A.length;
Set s = new HashSet<>();
Set dupeSet = new HashSet<>();
for(int i = 0; i < len; i++){
if(s.contains(A[i])) dupeSet.add(A[i]);
s.add(A[i]);
}
int[] res = new int[len - dupeSet.size()];
int index = 0;
for(int i = 0; i < len ;i++){
if(!dupeSet.contains(A[i])) res[index++] = A[i];
else dupeSet.remove(A[i]);
}
return res;

i*h2014-12-12 08:12

7 楼

等会我看下，先多谢了！

【在 z*********e 的大作中提到】

: 可能不算最优，扫两遍
: int len = A.length;
: Set s = new HashSet<>();
: Set dupeSet = new HashSet<>();
: for(int i = 0; i < len; i++){
: if(s.contains(A[i])) dupeSet.add(A[i]);
: s.add(A[i]);
: }
: int[] res = new int[len - dupeSet.size()];
: int index = 0;