那个数组找duplicate的面试题# Java - 爪哇娇娃
T*g
1 楼
Java其实有一个标准的class在util包里，叫做bitset，它实现了一个按需增长的位向
量。所以某个integer可以被表达成位向量的某一个位是否被值成了1.内存就省了。
量。所以某个integer可以被表达成位向量的某一个位是否被值成了1.内存就省了。
o*i
2 楼
找有没有可以用bitset，因为只有有/没有（0/1）两种可能
但是找重复，就有三种可能了，没有/有一个/重复，你bitset怎么搞？
【在 T*********g 的大作中提到】
: Java其实有一个标准的class在util包里，叫做bitset，它实现了一个按需增长的位向
: 量。所以某个integer可以被表达成位向量的某一个位是否被值成了1.内存就省了。
但是找重复，就有三种可能了，没有/有一个/重复，你bitset怎么搞？
【在 T*********g 的大作中提到】
: Java其实有一个标准的class在util包里，叫做bitset，它实现了一个按需增长的位向
: 量。所以某个integer可以被表达成位向量的某一个位是否被值成了1.内存就省了。
e*t
3 楼
folks,这题难道不是做加法？
【在 o***i 的大作中提到】
: 找有没有可以用bitset，因为只有有/没有（0/1）两种可能
: 但是找重复，就有三种可能了，没有/有一个/重复，你bitset怎么搞？
【在 o***i 的大作中提到】
: 找有没有可以用bitset，因为只有有/没有（0/1）两种可能
: 但是找重复，就有三种可能了，没有/有一个/重复，你bitset怎么搞？
T*g
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怎么搞？
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
5 楼
加法是简单的O(N)空间复杂度
复杂的要做交换，可以节省空间
【在 e*****t 的大作中提到】
: folks,这题难道不是做加法？
复杂的要做交换，可以节省空间
【在 e*****t 的大作中提到】
: folks,这题难道不是做加法？
z*3
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);
: }
类似用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
7 楼
会不会整数溢出呢?
【在 e*****t 的大作中提到】
: folks,这题难道不是做加法？
【在 e*****t 的大作中提到】
: folks,这题难道不是做加法？
b*i
8 楼
加法或者xor是O(1)空间复杂度，O(N)时间复杂度
【在 z*******3 的大作中提到】
: 加法是简单的O(N)空间复杂度
: 复杂的要做交换，可以节省空间
【在 z*******3 的大作中提到】
: 加法是简单的O(N)空间复杂度
: 复杂的要做交换，可以节省空间
T*g
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 的大作中提到】
: 这个从本质上说是O(N)的解法
: 类似用int来判断ascii用<>,&,|来判断的方法
: 做swap可以做出O(1)的解法
: 当N->无穷大的时候，还是很浪费空间
: good to know there is a class like this though
z*3
10 楼
早就有人写出来了
你自己不看
【在 T*********g 的大作中提到】
: cut the crap , show me your code
你自己不看
【在 T*********g 的大作中提到】
: cut the crap , show me your code
z*3
11 楼
对哦
想起来了
你说得对
【在 b***i 的大作中提到】
: 加法或者xor是O(1)空间复杂度，O(N)时间复杂度
想起来了
你说得对
【在 b***i 的大作中提到】
: 加法或者xor是O(1)空间复杂度，O(N)时间复杂度
o*i
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);
: }
【在 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);
: }
相关阅读
verawang.com 的网站样式，目前好像很流行。请问目前哪些大公司的平台是java做的，或是主要product是java写的呢？java后台开发有什么conference推荐么？eclipse的jetty服务started但8080口显示404 error吹牛吹多大合适?把photoshop文件PSD 转换成 HTML流行吗？Java会产生更多的page fault导致速度变慢问一个Java的问题，关于create generic arrayJava certification, 6 or 7?问个数组问题新手学Java 求建议Spring分布式应用的入门例子java update main UI from child thread issueRe: 代码糟糕，不一定是程序员水平差 (转载)最近公司在推vagarant vmNIO有必要学习吗？用惯了glassfish,突然要我用tomcat,真实不习惯。初级问题java学习范围 － for找工作jsp里，大家的submit button,是指向一个servlet,还是一个javascript function?