百度一道面试题

greemranqq

浏览: 975740 次
性别:
来自: 重庆

最近访客更多访客>>

wyj880303

northenwolf

地方疙瘩人

wuzijingaip

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

智力考场

百度面试寻找奇数算法 bitmap 算法位运算

那天看朋友提了一个百度面试的题目：怎么找出{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。有不正确的地方还请指正。

1
顶

3
踩

分享到：

面试经验分享--业务真的比技术重要？ | nio ---基本概念和使用

2014-05-21 11:43
浏览 5873
评论(31)
分类:编程语言
查看更多

11 楼 a719622178 2014-05-21

说白了程序员非要以程序员的思路限制住自己
往往跳不出自己的圈子
干嘛非得把程序员思路往自己身上扣
既然是面试既然题目没有硬性规定用程序思路解答
为什么就不能用更简单直接的思路解决一些问题往往比程序要快的多

反正我是仔细看过楼主的话了他说是复制的原话以程序员严谨的角度来推敲确实没说用什么思路解答只要给出答案就好了如果面试官有再要以程序的思路来解决或者是改口说这个题目的数据量其实很大那再换成程序思路好了

10 楼 renhongchao 2014-05-21

a719622178 写道

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

你真高端

9 楼 a719622178 2014-05-21

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

8 楼 yscyfy 2014-05-21

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

7 楼 qrg 2014-05-21

mfkvfn 写道

添加注释后的代码为

public class Test {
    public static void main(String[] args) {
        int[] nums = { 1, 1, 2, 3, 5, 3, 6, 8, 0, 7, 2, 3, 8, 3, 4, 4, 4, 5, 5, 5, 5 };
        int max = 10;
        // 能存放max位bit的short数组
        short[] bitArray = new short[(max + 7) >> 3];
        for (int num : nums) {
            set(bitArray, num);
        }
        // 输出结果
        for (int i = (bitArray.length << 3) - 1; i >= 0; i--) {
            boolean isOne = get(bitArray, i);
            if (isOne) {
                System.out.println(i);
            }
        }
    }

    // 常用位运算掩码
    private static final short[] BIT_MASKS = { 1, 2, 4, 8, 16, 32, 64, 128 };

    // 判断第n位是否为1
    private static boolean get(short[] bitArray, int n) {
        return (bitArray[index(n)] & BIT_MASKS[offset(n)]) != 0;
    }

    // 将第n位求反（0变1，1变0）
    private static void set(short[] bitArray, int n) {
        bitArray[index(n)] ^= BIT_MASKS[offset(n)];
    }

    // 找出第n位在short数组里的下标（除以8），如第1在shortArray[0]，第9位在shortArray[1]
    private static int index(int n) {
        return n >> 3;
    }

    // 找出第n位在shortArray[k]里的偏移量（对8求余数）
    private static int offset(int n) {
        return n ^ 0x00000007;
    }
}

测试能跑？

6 楼 mfkvfn 2014-05-21

添加注释后的代码为

public class Test {
    public static void main(String[] args) {
        int[] nums = { 1, 1, 2, 3, 5, 3, 6, 8, 0, 7, 2, 3, 8, 3, 4, 4, 4, 5, 5, 5, 5 };
        int max = 10;
        // 能存放max位bit的short数组
        short[] bitArray = new short[(max + 7) >> 3];
        for (int num : nums) {
            set(bitArray, num);
        }
        // 输出结果
        for (int i = (bitArray.length << 3) - 1; i >= 0; i--) {
            boolean isOne = get(bitArray, i);
            if (isOne) {
                System.out.println(i);
            }
        }
    }

    // 常用位运算掩码
    private static final short[] BIT_MASKS = { 1, 2, 4, 8, 16, 32, 64, 128 };

    // 判断第n位是否为1
    private static boolean get(short[] bitArray, int n) {
        return (bitArray[index(n)] & BIT_MASKS[offset(n)]) != 0;
    }

    // 将第n位求反（0变1，1变0）
    private static void set(short[] bitArray, int n) {
        bitArray[index(n)] ^= BIT_MASKS[offset(n)];
    }

    // 找出第n位在short数组里的下标（除以8），如第1在shortArray[0]，第9位在shortArray[1]
    private static int index(int n) {
        return n >> 3;
    }

    // 找出第n位在shortArray[k]里的偏移量（对8求余数）
    private static int offset(int n) {
        return n ^ 0x00000007;
    }
}

5 楼 mfkvfn 2014-05-21

我写的代码是这样的

    public static void main(String[] args) {
        int[] nums={1,1,2,3,5,3,6,8,0,7,2,3,8,3,4,4,4,5,5,5,5};
        int max=10;
        short[] bitArray=new short[(max+7)>>3];
        for(int num:nums){
            set(bitArray,num);
        }
        for(int i=(bitArray.length<<3)-1;i>=0;i--){
            boolean isOne=get(bitArray,i);
            if(isOne){
                System.out.println(i);
            }
        }
    }
    private static boolean get(short[] bitArray,int n){
        return  (bitArray[index(n)] & (short)(1<<offset(n)) )!=0;
    }
    
    private static void set(short[] bitArray,int n){
        bitArray[index(n)]^=1<<offset(n);
    }
    private static int index(int n){
        return n>>3;
    }
    private static int offset(int n){
        return n ^ 0x00000007;
    }

4 楼 greemranqq 2014-05-21

helongno1 写道

我也写了一下:

。。。

嗯，你的通过先排序的方式，然后加入字符串，然后再字符窃取是可以的，
但是从效率上来说，排序已经很耗时了，然后你
for (int i = 0; i < nums.length; i++) {
sb.append(nums[i]);
}
也耗时，包括后面的截取等等，我个人不推荐这种计算方式，尽量以遍历一次得结果，这样的方式做思考。
感谢你的分享~。~

3 楼 greemranqq 2014-05-21

mfkvfn 写道

为什么不用bit数组要用int数组？
可以用short模拟bit数组

是的，也可以用boolean 类型数组，不仅节省空间，而且计算的时候通过& 等运算会更快。这这里我仅仅留下了基本实现，不想写得太细的原因是：改进方法的人会得到更多的快乐，我实践过这样一种方式，当我看到别人写的东西超过我太多，甚至理解范围的时候，小东西还没什么，一旦代码或者其他方面太多，不能激发自己超越的兴趣。一旦发现别人写的东西仅仅是一个方面，还有优化的地方，还有不完善的地方的时候，更能激发乐趣~。~ 非常感谢你的建议

2 楼 helongno1 2014-05-21

我也写了一下:

      public static void main(String[] args) {

		int nums[] = { 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 5, 5 };
		StringBuffer sb = new StringBuffer();
		ArrayList<String> oddList = new ArrayList<String>();
		Arrays.sort(nums);

		for (int i = 0; i < nums.length; i++) {

			sb.append(nums[i]);
		}

		String numString = sb.toString();

		for (int i = 0; i < numString.length(); i++) {

			if (i != numString.length() - 1) {

				if (numString.charAt(i) != numString.charAt(i + 1)) {

					if (numString.substring(0, i + 1).length() % 2 != 0) {
						oddList.add(String.valueOf(numString.charAt(i)));
					}

					numString = numString.substring(i + 1, numString.length());

					i = -1;

				}

			} else {

				if (numString.length() % 2 != 0) {
					oddList.add(String.valueOf(numString.charAt(i)));
					break;
				}

			}

		}

		for (String string : oddList) {
			System.out.println(string);
		}

	}

1 楼 mfkvfn 2014-05-21

为什么不用bit数组要用int数组？
可以用short模拟bit数组

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论