当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

百度一道面试题

发表于: 2014-05-21   作者:greemranqq   来源:转载   浏览:
摘要: 那天看朋友提了一个百度面试的题目:怎么找出{1,1,2,3,3,4,4,4,5,5,5,5}  找出出现次数为奇数的数字.   我这里复制的是原话,当然顺序是不一定的,很多拿到题目第一反应就是用map,当然可以解决,但是效率不高。   还有人觉得应该用算法xxx,我是没想到用啥算法好...!   还有觉得应该先排序...   还有觉

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

 

百度一道面试题

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
依序遍历0到100闭区间内所有的正整数,如果该数字能被3整除,则输出该数字及‘*’标记;如果该数字
题目: 有一个N*N的矩阵,矩阵内的数字都是整数,包括正数、负数和0。起点是左上角,目的地是右下角
一 问题描述 给定一个含有n个元素的整形数组a,再给定一个和sum,求出数组中满足给定和的所有元素组
一 问题描述: 输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点
最近看到一个题目,是当在浏览器中输入一个url后回车,后台发生了什么?比如输入url后,你看到了百
最近看到一个题目,是当在浏览器中输入一个url后回车,后台发生了什么?比如输入url后,你看到了百
一、用CSS实现以下布局 让我们一起来做一个页面 首先,我们需要一个布局。 请使用CSS控制3个div,实
给你10分钟时间,根据上排给出十个数,在其下排填出对应的十个数 要求下排每个数都是先前上排那十个
问题: 一个大小为n的数组,里面的数都属于范围[0, n-1],有不确定的重复元素,找到至少一个重复元
第一部分:用CSS实现布局 请使用CSS控制3个div,实现如下图的布局: <div class="rightcontainer
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号