T*********g
发帖数: 496 | 1 Java其实有一个标准的class在util包里，叫做bitset，它实现了一个按需增长的位向
量。所以某个integer可以被表达成位向量的某一个位是否被值成了1.内存就省了。 | o***i
发帖数: 603 | 2 找有没有可以用bitset，因为只有有/没有（0/1）两种可能
但是找重复，就有三种可能了，没有/有一个/重复，你bitset怎么搞？
【在 T*********g 的大作中提到】
: Java其实有一个标准的class在util包里，叫做bitset，它实现了一个按需增长的位向
: 量。所以某个integer可以被表达成位向量的某一个位是否被值成了1.内存就省了。
| e*****t
发帖数: 1005 | 3 folks,这题难道不是做加法？
【在 o***i 的大作中提到】
: 找有没有可以用bitset，因为只有有/没有（0/1）两种可能
: 但是找重复，就有三种可能了，没有/有一个/重复，你bitset怎么搞？
| T*********g
发帖数: 496 | 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*******3
发帖数: 13709 | 5 加法是简单的O(N)空间复杂度
复杂的要做交换，可以节省空间
【在 e*****t 的大作中提到】
: folks,这题难道不是做加法？
| z*******3
发帖数: 13709 | 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*********g
发帖数: 496 | 7 会不会整数溢出呢?
【在 e*****t 的大作中提到】
: folks,这题难道不是做加法？
| b***i
发帖数: 3043 | 8 加法或者xor是O(1)空间复杂度，O(N)时间复杂度
【在 z*******3 的大作中提到】
: 加法是简单的O(N)空间复杂度
: 复杂的要做交换，可以节省空间
| T*********g
发帖数: 496 | 9 cut the crap , show me your code
【在 z*******3 的大作中提到】
: 这个从本质上说是O(N)的解法
: 类似用int来判断ascii用<<,>>,&,|来判断的方法
: 做swap可以做出O(1)的解法
: 当N->无穷大的时候，还是很浪费空间
: good to know there is a class like this though
| z*******3
发帖数: 13709 | 10 早就有人写出来了
你自己不看
【在 T*********g 的大作中提到】
: cut the crap , show me your code
| z*******3
发帖数: 13709 | 11 对哦
想起来了
你说得对
【在 b***i 的大作中提到】
: 加法或者xor是O(1)空间复杂度，O(N)时间复杂度
| o***i
发帖数: 603 | 12 赞！
【在 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);
: }
|
|
