百度一道面试题

那天看朋友提了一个百度面试的题目：怎么找出{1,1,2,3,3,4,4,4,5,5,5,5}  找出出现次数为奇数的数字.

 

我这里复制的是原话，当然顺序是不一定的，很多拿到题目第一反应就是用map,当然可以解决，但是效率不高。

 

还有人觉得应该用算法xxx,我是没想到用啥算法好...！

 

还有觉得应该先排序...

 

还有觉得用位图....bitmap 等等方法！

 

我都觉得麻烦，思维方式就是，从节省时间考虑，从数组来看，我们都得遍历一次数组里面的元素，那么我就想只遍历一次，就能得到结果的方法，然后由算法去优化，这是我通常考虑类似问题的办法。

 

第一种情况：

由于数组元素限定，我们先假设我们能知道最大的数字，我这里用另一组数据测试：

{1,1,2,3,5,3,6,8,7,2,3,8,3,4,4,4,5,5,5,5};

可以看出8 是最大的数字，那么我就可以建立一个长度为9的数组index[]，只要出现一次数字，就在相应的位置++。

比如数字1 ,那么我就在index[1] ++ .进行处理，那么循环一次之后我就知道每个元素出现的次数。

 

但是还得循环去判断是奇数还是偶数，这里做点小改进，在存放的时候就可以判断。比如，1 出现一次，我就在index[1] 的位置 设置为1，出现第二次，我就让index[1] 的位置变为0， 那么数组里面只要为1 的，都是出现的奇数，并且位置和元素等价，可以看代码。

 

static int[] nums = {1,1,2,3,5,3,6,8,0,7,2,3,8,3,4,4,4,5,5,5,5};
	// 我假设我知道元素最大的数
	static int maxNum = 9;
	static int[] index = new int[maxNum];
	public static void main(String[] args) {
		// 计算个数
		for(int i =0;i<nums.length;i++){
			index[nums[i]] = ++index[nums[i]]/2 == 1?0:1;
		}
		// 打印
		for(int i=0;i<index.length;i++){
			if(index[i] == 1){
				System.out.println("出现次数为奇数的数字有："+i);
			}
		}
	}

 

 

 

OK，有人觉得不知道元素的最大数，这里有几种方案解决这种问题.

1.你可以直接建立一个大数组，Integer 的最大值的，当然里面必须是int 范围的。这样会浪费很多空间。

2.你可以给一个默认值，比如100，如果发现nums[i] 的值，大于数组长度了，那么就要进行扩容了， 值可以设大点，看你作何做出权衡。

 

小结：

      1.这里仅仅提供一种思路，还不完善，可以进行修改，有更好的欢迎提供，非常感谢。

      2.改进建议，能否节约空间，因为发现index 数组里面只需要为1 的，表示奇数的数，其他的浪费空间了。 还有算 ++ 操作 ，三目运算能否考虑算法，让执行能力更快，这些就交给有兴趣的朋友去啦，有东西了，希望分享哦~。~

 

 ———————————————————————————————————————————————

                                                             分   割    线

———————————————————————————————————————————————

 

看大家这么有兴趣，这里我综合了了一下意见：

第一种，按我的方法进行微量优化，不建立int,建立boolean ，节约空间

	static int[] nums = {1,1,2,3,5,3,6,8,0,7,2,3,8,3,4,4,4,5,5,5,5,9,9,1024*1024*100};  
    // 我假设我知道元素最大的数  +1
    static int maxNum = 1024*1024*100+1;  
    static boolean[] index = new boolean[maxNum];
    public static void main(String[] args) {  
        // 计算个数  
        for(int i =0;i<nums.length;i++){  
            index[nums[i]] = index[nums[i]]^true == false?false:true;  
        }  
        // 打印  
        for(int i=0;i<index.length;i++){  
            if(index[i]){  
                System.out.println("出现次数为奇数的数字有："+i);  
            }  
        }  
    } 

 

可以看出上面所占的字节数至少要1024*1024*100+1 也就是100M的空间，我们可以通过命令：

-Xmx64m -Xms64m 只允许64M，那么这里就OOM了

 

第二种，这里我采用5L的办法，做了一点改进，为了方便理解这个，我也做了详细的解释：

static int[] nums = {1,1,2,3,5,3,6,8,0,7,2,3,8,3,4,4,4,5,5,5,5,9,9,1024*1024*100*3};  
	// 我假设我知道元素最大的数
	static int max = 1024*1024*100*3+1;
	static byte[] bits = new byte[(max + 7) >> 3];

	public static void main(String[] args) {
		
		
		// 计算
		for (int i = 0; i < nums.length; i++) {
			set(nums[i]);
		}
		// 输出
		for (int i = (bits.length << 3) - 1; i >= 0; i--) {
			if (get(i)) {
				System.out.println(i);
			}
		}
	}

	// 第一步，求出该数应该放在byte 数组哪个位置,相当于n/8 得出位置
	// 比如1~7 之间的放[0] 相当于1~7/8  位置，8~15[1] 8~15/8位置，依次类推
	public static int index(int n) {
		return n >> 3;
	}

	// 第二步，计算n在数组里面的偏移量，比如：3%8 = 3,在数组里面的位置我们应该放在0000 0100 这种表示
	public static int offset(int n) {
		return n & 0x07;
	}

	// 第三步，刚才的位置和偏移量做异或运算，做异或的原因就是当出现偶数次的时候 进行归0
	// 比如假设第一个数字 3，计算位置在[0] 的位置。默认 [0] 的bit 元素二进制：
        // {0000 0000}
	// 那么第一次就将1 << 3位，二进制是：0000 00001 << 3 == 0000 0100 ，然后将和[0] 位         // 置的做异或运算
	// 0000 0000
	// ^0000 0100
	// 0000 0100 这表示已经存放了一次值：3
	// 如果第二个元素还是3,再次操作就变成了：0000 0000,就归0了
	public static void set(int n) {
		bits[index(n)] ^= (1 << offset(n));
	}

	// 获取位置的元素，从最高位开始遍历，假设bit数组两个长度分别是：
	// [0]=>{0000 1000} 3
	// [1]=>{0010 0100} 13 10
	// 总长度也就是16位，当我们获取get[15] 的时候，
	// 以同样的方式可以得到15/8 = 7的位置在[1] 里面的最高位,也就是0
	// 如果是get[3],那么获取的就是[0],4/8 = 4 位置的1,这里位置通过位移操作完成的
	public static boolean get(int i) {
		return (bits[index(i)] & 1 << offset(i)) != 0;
	}

 

可以看出，我们允许的范围增加了很多，理论上可以增加8倍。

 

关于内存限制这块，可以通过命令：

Runtime r = Runtime.getRuntime();
System.out.println(r.totalMemory()/1024/1014);
System.out.println(r.maxMemory()/1024/1014);
System.out.println(r.freeMemory()/1024/1014);
大概估计，但是我们并不能建立一个byte[r.maxMemory()] 我JDK1.7 的限制在r.maxMemory()*0.69 就
OOM了，我记得可以通过命令调节，但是- -忘记命令了。

 

 

小结：

    1.很高兴大家有兴趣来研究这种小算法，更加熟悉嘛。

    2.关于评论的算法，我尝试了，有数组越界，得不到正确结果等，需要改进，可以尝试增大数据进行

    3.算法同样是不完善的，还有改进的余地，多专研啦~。~ 还有一些边界问题，考虑不周。

       4.关于bit 类似的计算，可以专门花时间看看，可以尝试大文件的的一些处理哦

       5。有不正确的地方还请指正。

 

评论

31 楼 greemranqq 2014-06-08  

stellari 写道

博主的讨论很深入。但是，我个人觉得这个题真的不如用hashmap或者hashset。 博主的方法其实相当于自己实现了一个特殊的hashmap。这个hashmap完全不存在collision，但是所需的空间和输入数组的值范围相关（而不是和数组的长度相关），而这个值可能非常大。比如即使输入的数组非常短{0, 0, 0, INT_MAX}，也会耗掉2G的内存。另外一个用bitmap其实本质上就是个hashset，在空间上要比前者优化得多（在全部元素是正整数的情况下<=500MB）。用hashmap和hashset可能会慢些，但是总时间复杂度基本上还是O(N)，好处在代码实现上要方便得多，而且后期维护也会更容易。当然，这些选择都是各有利弊，面试时都讨论一下应该是个很不错的选择。

谢谢 分享，API的hash有些不合适，单独写一个还是可行的，实际应用中得在空间和时间上做权衡了

30 楼 stellari 2014-06-06  

博主的讨论很深入。但是，我个人觉得这个题真的不如用hashmap或者hashset。 博主的方法其实相当于自己实现了一个特殊的hashmap。这个hashmap完全不存在collision，但是所需的空间和输入数组的值范围相关（而不是和数组的长度相关），而这个值可能非常大。比如即使输入的数组非常短{0, 0, 0, INT_MAX}，也会耗掉2G的内存。另外一个用bitmap其实本质上就是个hashset，在空间上要比前者优化得多（在全部元素是正整数的情况下<=500MB）。用hashmap和hashset可能会慢些，但是总时间复杂度基本上还是O(N)，好处在代码实现上要方便得多，而且后期维护也会更容易。当然，这些选择都是各有利弊，面试时都讨论一下应该是个很不错的选择。

29 楼 greemranqq 2014-06-03  

jahu 写道

greemranqq 写道

jahu 写道

我表示，，对于你的方法有点无语，，
没错，布尔是最初始的使用，当时考虑扩张性没有。
用位计算，，，空间是小了，，那么速度了？
java的位计算本生， 是伪位计算。

1.对于扩张性，这确实也要受内存等因素限制，当然从面试题来说，会有一定考虑，但是扩张性也不会无限放大。对于数字或者一些字符串的做法，还是可以这样计算的。

2.关于java s的伪位计算，我这里确实没有更好的计算方式，我不知道JAVA 还有什么计算方式能快过这种，能否指点一下？

3.关于速度问题，这里因为涉及到“伪位计算”的问题，这是我能做到的最快速度了。

4.如果你有更好的方案，可以提出来，给大家分享分享，谢谢~.~!

你确定java的位计算是最快的吗？

JAVA 的位运算，更亲近于计算机进制级的的运算，当然你说的 “伪位计算” 我是第一次听说，不明白原理。我也不能确定位运算是JAVA 里面最快的，但是我的知识里面能找到最快的，还有什么更快的？能说一下吗？

28 楼 jahu 2014-06-03  

greemranqq 写道

jahu 写道

我表示，，对于你的方法有点无语，，
没错，布尔是最初始的使用，当时考虑扩张性没有。
用位计算，，，空间是小了，，那么速度了？
java的位计算本生， 是伪位计算。

1.对于扩张性，这确实也要受内存等因素限制，当然从面试题来说，会有一定考虑，但是扩张性也不会无限放大。对于数字或者一些字符串的做法，还是可以这样计算的。

2.关于java s的伪位计算，我这里确实没有更好的计算方式，我不知道JAVA 还有什么计算方式能快过这种，能否指点一下？

3.关于速度问题，这里因为涉及到“伪位计算”的问题，这是我能做到的最快速度了。

4.如果你有更好的方案，可以提出来，给大家分享分享，谢谢~.~!

你确定java的位计算是最快的吗？

27 楼 greemranqq 2014-06-02  

jahu 写道

我表示，，对于你的方法有点无语，，
没错，布尔是最初始的使用，当时考虑扩张性没有。
用位计算，，，空间是小了，，那么速度了？
java的位计算本生， 是伪位计算。

1.对于扩张性，这确实也要受内存等因素限制，当然从面试题来说，会有一定考虑，但是扩张性也不会无限放大。对于数字或者一些字符串的做法，还是可以这样计算的。

2.关于java s的伪位计算，我这里确实没有更好的计算方式，我不知道JAVA 还有什么计算方式能快过这种，能否指点一下？

3.关于速度问题，这里因为涉及到“伪位计算”的问题，这是我能做到的最快速度了。

4.如果你有更好的方案，可以提出来，给大家分享分享，谢谢~.~!

26 楼 jahu 2014-06-02  

我表示，，对于你的方法有点无语，，
没错，布尔是最初始的使用，当时考虑扩张性没有。
用位计算，，，空间是小了，，那么速度了？
java的位计算本生， 是伪位计算。

25 楼 greemranqq 2014-05-22  

a719622178 写道

面试题吗 而且没说用程序解答啊 直接数就可以了 2 跟 4 啊
要是用程序思路解决的话 再考虑喽
大脑都被程序员思路给锈住了吗~~~

呵呵，是的，程序员思维 固定了~。~ 谢谢 提点.

24 楼 greemranqq 2014-05-22  

yscyfy 写道

其实你的算法说白了就是bitmap啊，你怎么还说我都觉得麻烦？
直接使用java中的bitset类就好了，其他的没什么必要吧

我模拟了bit 位，但是不是bitmap,没采用那些位位运算，bitset 我没用过 尴尬，看了下，害的研究研究

23 楼 qq392447199 2014-05-22  

我觉得这样还是不好，那万一有100个数字呢?我还是觉得用map好，但是value用true和false来弄，第一次设置true，在重复一个用false，然后在true。

22 楼 shinestmt 2014-05-22  

int[] nums = {1,1,2,3,5,3,6,8,0,7,2,3,8,3,4,4,4,5,5,5,5};
List<Integer> result = new LinkedList<>(); 

for (int i : nums) {
	if(result.contains(i)){
		result.remove(Integer.valueOf(i));
		continue;
	}
	result.add(i);
}
// 输出结果
for (Integer i : result) {
	System.out.println(i);
}

这样行么？

21 楼 qrg 2014-05-22  

jahu 写道

那里下标越界了？
我也打算用布尔型的，，考虑到可扩展性，，没有使用。你的代码跟我的代码。多少区别

qrg 写道

如果数组中的数值均为正数时。

int[] nums = { 1, 1, 2, 3, 5, 3, 6, 8, 0, 7, 2, 3, 8, 3, 4, 4, 4, 5, 5,
                5, 5 };

        Arrays.sort(nums);
        int maxNum = nums[nums.length - 1] + 1;

        boolean[] oddNum = new boolean[maxNum];

        for (int i = 0; i < nums.length; i++) {
            oddNum[nums[i]] = !oddNum[nums[i]];
        }

        for (int j = 0; j < oddNum.length; j++) {
            if (oddNum[j]) {
                System.out.println("In nums array, Number(Index) '" + j
                        + "' appears odd times.");
            }
        }

排序的部分性能有待优化。

另外，关于区别：我的里边除了在输出结果上用了一次判断，没有乱七八糟的判断...当然，关于输入的数组，任意长度都可以了。

20 楼 qrg 2014-05-22  

jahu 写道

那里下标越界了？
我也打算用布尔型的，，考虑到可扩展性，，没有使用。你的代码跟我的代码。多少区别

qrg 写道

如果数组中的数值均为正数时。

int[] nums = { 1, 1, 2, 3, 5, 3, 6, 8, 0, 7, 2, 3, 8, 3, 4, 4, 4, 5, 5,
                5, 5 };

        Arrays.sort(nums);
        int maxNum = nums[nums.length - 1] + 1;

        boolean[] oddNum = new boolean[maxNum];

        for (int i = 0; i < nums.length; i++) {
            oddNum[nums[i]] = !oddNum[nums[i]];
        }

        for (int j = 0; j < oddNum.length; j++) {
            if (oddNum[j]) {
                System.out.println("In nums array, Number(Index) '" + j
                        + "' appears odd times.");
            }
        }

排序的部分性能有待优化。

呵呵，老兄，在nums里边把8换成200，你测试一下...

19 楼 forestking 2014-05-22  

int a = 0;
for each elem b in the array
  if( a & b == b) a = a ^ b
  else a = a | b

for each elem b in the array
  if( a & b == b)
    output b

18 楼 jahu 2014-05-22  

那里下标越界了？
我也打算用布尔型的，，考虑到可扩展性，，没有使用。你的代码跟我的代码。多少区别

qrg 写道

如果数组中的数值均为正数时。

int[] nums = { 1, 1, 2, 3, 5, 3, 6, 8, 0, 7, 2, 3, 8, 3, 4, 4, 4, 5, 5,
                5, 5 };

        Arrays.sort(nums);
        int maxNum = nums[nums.length - 1] + 1;

        boolean[] oddNum = new boolean[maxNum];

        for (int i = 0; i < nums.length; i++) {
            oddNum[nums[i]] = !oddNum[nums[i]];
        }

        for (int j = 0; j < oddNum.length; j++) {
            if (oddNum[j]) {
                System.out.println("In nums array, Number(Index) '" + j
                        + "' appears odd times.");
            }
        }

排序的部分性能有待优化。

17 楼 qrg 2014-05-22  

如果数组中的数值均为正数时。

int[] nums = { 1, 1, 2, 3, 5, 3, 6, 8, 0, 7, 2, 3, 8, 3, 4, 4, 4, 5, 5,
                5, 5 };

        Arrays.sort(nums);
        int maxNum = nums[nums.length - 1] + 1;

        boolean[] oddNum = new boolean[maxNum];

        for (int i = 0; i < nums.length; i++) {
            oddNum[nums[i]] = !oddNum[nums[i]];
        }

        for (int j = 0; j < oddNum.length; j++) {
            if (oddNum[j]) {
                System.out.println("In nums array, Number(Index) '" + j
                        + "' appears odd times.");
            }
        }

排序的部分性能有待优化。

16 楼 qrg 2014-05-22  

jahu 写道

引用

static int[] nums = {1,1,2,3,5,3,6,8,0,7,2,3,8,3,4,4,4,5,5,5,5}; 
@Test
public void timeZone(){
int leng = nums.length;
int i = 0 , num=0,y = 0;
int[] by = new int[leng];
for( ; ;){
num = nums[i++];
by[num] = by[num]^1;
if(y<num){
y = num;
}
if(i == leng){
i = 0;
break;
}
}
for( ; ;){
if(by[i] == 1){
System.out.println(i +"是存在的个数奇数");
}
i++;
if(i == y){
break;
}
}
}

你这个有数组越界的问题，当待检查数组中的最大数值超过待检查数组的长度时，by数据就越界了....

15 楼 jahu 2014-05-22  

引用

static int[] nums = {1,1,2,3,5,3,6,8,0,7,2,3,8,3,4,4,4,5,5,5,5}; 
@Test
public void timeZone(){
int leng = nums.length;
int i = 0 , num=0,y = 0;
int[] by = new int[leng];
for( ; ;){
num = nums[i++];
by[num] = by[num]^1;
if(y<num){
y = num;
}
if(i == leng){
i = 0;
break;
}
}
for( ; ;){
if(by[i] == 1){
System.out.println(i +"是存在的个数奇数");
}
i++;
if(i == y){
break;
}
}
}

14 楼 jahu 2014-05-22  

优化了一下发发表的，
static int[] nums = {1,1,2,3,5,3,6,8,0,7,2,3,8,3,4,4,4,5,5,5,5}; 
@Test
public void timeZone(){
int leng = nums.length;
int i = 0 , num=0,y = 0;
int[] by = new int[leng];
for( ; ;){
num = nums[i++];
by[num] = by[num]^1;
if(y<num){
y = num;
}
if(i == leng){
i = 0;
break;
}
}
for( ; ;){
if(by[i] == 1){
System.out.println(i +"是存在的个数奇数");
}
i++;
if(i == y){
break;
}
}
}

13 楼 jahu 2014-05-22  

你们的好复杂啊，，，，我有一个更加简单的方法，

12 楼 evanzzy 2014-05-21  

看不明白这题。

数组的长度有限制吗？里面的数字只是1到5还是正负无穷？是否包含小数？数字的排列是否有规律还是乱序的？是找出一个出现次数为奇数的数字还是所有？

限制条件不一样，解法差别比较大的。