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

编程之美-快速找出故障机器

发表于: 2012-07-01   作者:bylijinnan   来源:转载   浏览:
摘要: package beautyOfCoding; import java.util.Arrays; public class TheLostID { /*编程之美 假设一个机器仅存储一个标号为ID的记录,假设机器总量在10亿以下且ID是小于10亿的整数,假设每份数据保存两个备份,这样就有两个机器存储了同样的数据。 1.假设在某个时间得到一个数据文件ID的列表,是
package beautyOfCoding;

import java.util.Arrays;

public class TheLostID {

	/*编程之美 
	 假设一个机器仅存储一个标号为ID的记录,假设机器总量在10亿以下且ID是小于10亿的整数,假设每份数据保存两个备份,这样就有两个机器存储了同样的数据。
		1.假设在某个时间得到一个数据文件ID的列表,是否能快速地找出表中仅出现一次的ID?即快速找出出现故障的机器存储的数据ID。
        2.如果有两台机器出现故障呢?(假设存储同一份数据的两台机器不会同时出现故障,即列表中缺少的是两个不等的ID)
	 这里只考虑第2个问题:有两台机器出现故障,且缺少的是两个不等的ID
	 书上的解法4通过构造方程来解答,这有个前提是,需要知道所有的ID
	 我认为解法三(异或)更好
	 以下是解法三的实现
	 */
	public static void main(String[] args) {
		
		int[] c = {1,2,3,4,10,1,2,3,6,6};//ID列表
		TheLostID lostID = new TheLostID();
		lostID.process(c);
	}

	public void process(int[] c){
		if(c==null||c.length<4){//ID列表至少应该有4个ID
			return;
		}
		if(this.isValidInput(c)){
			this.find(c);
		}
	}
	
	/*
	 例如,对于数组{1,2,3,4,10,1,2,3},所有数字异或的结果是:
	 xor=4^10=(1110)-->最低位的1在倒数第二位(这个位置记为i位),表示4和10在i位是不相等的
	 那么,数组里面的数字可分为两组:一组是在i位上为1,另一组为0
	 让这两组数字各自内部异或,则能找到只出现一次的4和10
	 */
	public void find(int[] c){
		int len=c.length;
		int xor=0;
		for(int i=0;i<len;i++){
			xor ^=c[i];
		}
		int xor2=xor&(xor-1);//去掉xor二进制表示里面最低位的1
		int lastDiffBit=xor^xor2;//x,y在这一位是不相等的,一个为0,一个为1
		int x=0;
		int y=0;
		for(int i=0;i<len;i++){
			if((c[i]&lastDiffBit)==lastDiffBit){
				x ^=c[i];
			}else{
				y ^=c[i];
			}
		}
		System.out.println("x,y="+x+","+y);
	}
	
	/*
	判断数组是否符合以下条件:
	1、数组里面的数字,要么出现一次,要么出现两次
	2、出现一次的数字,有且只有两个
	最快的方法当然是用哈希表
	这里用的是 排序+遍历统计(如果数据量大,用排序也不如哈希表好)
	*/
	public boolean isValidInput(int[] c){
		Arrays.sort(c);//排序
		int len=c.length;
		int count=0;
		if(c[0]!=c[1]){
			count++;
		}
		if(c[len-1]!=c[len-2]){
			count++;
		}
		for(int i = 0;i<len;i++){
			if(i<=len-3){
				if(c[i]==c[i+1]&&c[i+1]==c[i+2]){//不能存在三个相等的数
					return false;
				}
			}
			//统计不相等的数有几个
			if(0<i&&i<len-1&&c[i]!=c[i-1]&&c[i]!=c[i+1]){
				count++;
			}
			if(count>2){
				return false;
			}
		}
		return count==2;
	}
}

编程之美-快速找出故障机器

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
3、题目:能否快速找出一个数组(简单起见,数组中元素值各不一样)中的两个数字,让这两个数字之和
今天开始看编程之美 。第一个问题是CPU的使用率控制,微软的问题果然高大上,我一看就傻了,啥也不
第一章 软件架构是什么 软件架构应该... asoftware architect that the system should be friendly
给定一个前序和中序变量的结果,写一个算法重建这棵树:如: 前序: a b d c e f 中序: d b a e c f
还好看到了,这个以前好早见到过。 用得是辗转相除法。 k =x/y b=x%y 则 x = ky+b 如果一个整数能够
题目:编写一个函数,把一个char组成的字符串循环右移n位。例如:原来是”abcdefghi”,如果n = 2,
Windows中有一项功能,是可以在任务管理器中查看CPU的使用率,管理器以图形使用率在不同的时间点的
一 年又很快过去了,今年从之前的设计师转型到Android程序员。期间也经历了许多的坎坎坷坷,从一个
编程之美:平面最近点对 一.概念引入 最接近点对问题的提法是:给定平面上n个点,找其中的一对点,使
《 编程之美》中有个关于逐层遍历二叉树的算法: /// <summary> /// 结点类 /// </summary
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号