那个数组找duplicate的面试题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Java - 爪哇娇娃

那个数组找duplicate的面试题

那个数组找duplicate的面试题# Java - 爪哇娇娃

T*g2013-05-24 07:05

1 楼

Java其实有一个标准的class在util包里，叫做bitset，它实现了一个按需增长的位向
量。所以某个integer可以被表达成位向量的某一个位是否被值成了1.内存就省了。

o*i2013-05-24 07:05

2 楼

找有没有可以用bitset，因为只有有/没有（0/1）两种可能
但是找重复，就有三种可能了，没有/有一个/重复，你bitset怎么搞？

【在 T*********g 的大作中提到】

: Java其实有一个标准的class在util包里，叫做bitset，它实现了一个按需增长的位向
: 量。所以某个integer可以被表达成位向量的某一个位是否被值成了1.内存就省了。

e*t2013-05-24 07:05

3 楼

folks,这题难道不是做加法？

【在 o***i 的大作中提到】

: 找有没有可以用bitset，因为只有有/没有（0/1）两种可能
: 但是找重复，就有三种可能了，没有/有一个/重复，你bitset怎么搞？

T*g2013-05-24 07:05

4 楼

public class FindDuplicate {
public static void main(String[] args) {
int[] input = {1, 2, 3, 4, 5, 6, 1, 3, 4};
BitSet bitSet = new BitSet();
for (int i : input) {
if (bitSet.get(i)) {
System.out.println("duplicate is " + i);
} else {
bitSet.set(i);
}
}
}
}
呵呵

【在 o***i 的大作中提到】

: 找有没有可以用bitset，因为只有有/没有（0/1）两种可能
: 但是找重复，就有三种可能了，没有/有一个/重复，你bitset怎么搞？

z*32013-05-24 07:05

5 楼

加法是简单的O(N)空间复杂度
复杂的要做交换，可以节省空间

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

: folks,这题难道不是做加法？

z*32013-05-24 07:05

6 楼

这个从本质上说是O(N)的解法
类似用int来判断ascii用<>,&,|来判断的方法
做swap可以做出O(1)的解法
当N->无穷大的时候，还是很浪费空间
good to know there is a class like this though

【在 T*********g 的大作中提到】

: public class FindDuplicate {
: public static void main(String[] args) {
: int[] input = {1, 2, 3, 4, 5, 6, 1, 3, 4};
: BitSet bitSet = new BitSet();
: for (int i : input) {
: if (bitSet.get(i)) {
: System.out.println("duplicate is " + i);
: } else {
: bitSet.set(i);
: }

T*g2013-05-24 07:05

7 楼

会不会整数溢出呢?

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

: folks,这题难道不是做加法？