1. 问题:100个连续
的数打乱
之后,随机取出1个数
,问如何最快速
的判断出少了哪一个?
分析:对于所有100个连续的数,只要除余100。一定在0~99之间。一般来说,比较常规的做法就是先排序(利用Hash表定位),在循环查找。当然时间复杂度是O(2n)。现在介绍一种很牛的O(n)做法:求二进制异或运算。
异或运算: 0^0=1^1=0; 0^1=1^0=1。0~99个数全部异或的结果只能是0。如果缺少一个数,那么全部异或的结果正好就是那个数。为什么呢?我们做个小实验:假如有四个数: 0001 0010,0101, 0110 排列成一个matrix.
bits: 1 2 3 4
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 0
全部异或: 0 0 0 0
我们可以下结论了,要全部异或的结果为0,那么所有bit位上的1的个数必须为偶数。
反过来说:如果其中有一个数不存在了(比如0001),那么少0的的bit位上的值不变(因为1的个数还是偶数),而少1的bit位上的值就变成了1(1的个数为奇数了)。
这样0~99的道理也就一样了,所以异或的结果就是少的那个值。代码如下:
int data=0;
for(int i=1;i<=99;i++){
if(i==78) //少78
continue;
data=data^i;
}
System.out.println(data);
2. 问题:100个连续
的数打乱
之后,随机取出2个数
,问如何最快速
的判断出少了哪两个? (注意少2个数了)
分析:常用的做法可以先创建一个100个结构的Hash表,然后循环一次将所有数哈希100之后的位置上置1。然后顺序循环100次查找这个Hash表。前后需要O(2n)的时间。然而有没有更快速的做法呢?当然,直接操作bit.
假设我们有32个连续打乱的数字(0~31)缺少两个数2和11,希望把标记1标记在一个32位上。也就是一个整形变量,标记完之后就成为了:
bits position 31 30 29 28 ....... 11 10 .... 2 1 0
int a= 1 1 1 1 ....... 0 1 .... 0 1 1 (缺少数的bit位上为0)
至于如何标记成为a,我们可以看看下面的小段代码:
long bits=0;
for(int i=0;i<32;i++){
long bitMove=1;
if(i==2||i==11)
continue;
bitMove=bitMove<<i;
bits=bits | bitMove;
System.out.println(bits+" : "+Long.toBinaryString(bits));
}
此时我们将数字a每8位作为一个数字b,如果b==255, 则说明全部8位都是1(没有缺少数字)。如果b!=255,则说明有某些位是0(有数字缺少),然后再在不等于255的8 bits上顺序查找等译0的位数即可。这样就相当于原来需要顺序查找32 bits(查找32次)。而现在只需要先查找4个8位的块,然后再需找某个8位块中的bit(也就是需要4+8=12次)即可。这就是分块查找的基本原理了。
通过一个32个连续的数,我们发现了敲门。这样对于100个连续的数呢?很简单,我们需要4个32位就够了。注意:由于最高位如果是1的话,整形数据将会变成负数,不方便我们的计算。因此我们用long数据来存储32个位数。
代码如下:
public class Test{
public static void main(String[] args){
//需要4个32位数据,用long存储为了避开int存储可能带来的负数。
//intBits[0]的最低32位标识数据0~31
//intBits[1]的最低32位标识数据32~63,
//intBits[2]的最低32位标识数据64~95,
//intBits[3]的最低4位标识数据96~99
long[] intBits={0L,0L,0L,0L};
//用100bit位标识是否存在0~99的数据
//此时需要循环的次数为100次,时间复杂度O(n),n为连续的data数量。
int loop=0;
for(int data=0;data<=99;data++){
long bitMove=1;
if(data==2||data==11) //缺少数据2和11
continue;
bitMove=bitMove<<(data-32*(data/32));
intBits[data/32]=intBits[data/32] | bitMove;
loop++;
}
//中间打印标识结果
System.out.print("标识结果(循环"+loop+"次):");
for(int i=3;i>=0;i--)
System.out.print(Long.toBinaryString(intBits[i]));
System.out.println();
//分块查找,每8bit一块,一共需要100/8=13块
//其中如果8bit全部是1,则该数据等于2^8-1=255
//前3个intBits都全部位数都用来标识数据
loop=0;
int zeroSize=0;
for(int i=0;i<4;i++){
long bits=intBits[i];
long eightBits=0;
int eightSize=0;
while((eightBits=bits%256)!=0){
System.out.println("第"+((eightSize+1)+i*4)+"个8bits块:"+Long.toBinaryString(eightBits));
if(i<3&&eightBits!=255){
for(int j=0;j<8;j++){
loop++;
if(eightBits%2==0){
zeroSize=j+eightSize*8+i*32;
System.out.println(" zero size="+zeroSize);
}
eightBits=eightBits>>1;
}
}
bits=bits/256;
eightSize++;
loop++;
}
}
System.out.println("标识后查找需要循环"+loop+"次");
}
}
这段代码只需要循环98+29=117次,少于一般情况下的200次。
3. 问题:有1到10w这10w个数,去除2个并打乱次序,如何找出那两个数?(不准用位图)
我想用分块查找的思想,首先开辟一个a[100][1001]存储结构,遍历10W个数存放这个结构
int[][] a=new[100][1001];
for(int i=0;i<99998){
a[i/1000-1][i%1000+1]=1;
a[i/1000-1][0]++; //记1000个数是否已经满了。
}
for(int j=0;j<100;j++){
if(a[j][0]<1000){ //这1000个数里面有数少了
for(int k=1;k<1000;i++){
if(a[j][k]!=1){
System.out.println("少了的呢个数就是:"+(j*1000+k));
}
}
}
}
性能分析:
首先循环99998次为数组设置标志位。然后双重循环(其实真正需要双循环的是有2次,因为就少了2个数),因此双重循环的次数因该是: 100(块查找次数)+2*1000=2100次。
一共循环99998+2100 因此效率是O(n+m) 其中n为待查找数字的个数(10W),m为分割的块数与快内查找的次数。如果n远远大于m,则查询效率接近于O(n)。因此这种查找数据越多效率越好。
分享到:
相关推荐
相比之下,中部地区和西部地区的数字科技专利申请量相对较少,但中部的安徽省和西部的重庆市表现相对较好,显示出一定的发展潜力。 在企业层面,腾讯成为了广东省数字科技专利申请的领头羊。腾讯能够占据这一位置,...
本文将深入讲解如何在Android应用中集成腾讯定位服务,并判断网络连接状态。 首先,我们需要在AndroidManifest.xml文件中添加必要的权限,包括网络访问权限和定位权限: ```xml ``` 接下来,需要在项目中引入...
腾讯信用评分是什么?腾讯信用分用法及提高方法 腾讯信用评分是什么? 腾讯信用评分是基于历史行为信息,通过采集不同维度的信息,运用大数据,机器学习以及传统统计方法相结合的技术手段来客观的反映用户的信用...
腾讯TDC数字农村解决方案.pdf
腾讯和阿里组织变革的战略意义 在企业战略管理中,组织变革是一个非常重要的策略工具。通过组织变革,企业可以更好地适应市场变化,抓住新的发展机遇,增强自己的竞争优势。腾讯和阿里的组织变革,就是一个典型的...
在Android开发中,调用第三方地图导航应用如高德、百度和腾讯,是常见的功能需求。这涉及到系统级的意图(Intent)操作,以及不同坐标系之间的转换。本篇文章将详细探讨这些知识点。 首先,调用第三方导航应用通常...
腾讯是中国最大的互联网综合服务提供商之一,成立于1998年11月,在全球范围内拥有众多用户。腾讯致力于通过互联网服务提升人类生活品质,并将“一切以用户价值为依归”作为经营理念。2004年6月16日,腾讯在香港...
腾讯全球数字生态大会:5G车路协同创新应用白皮书
腾讯微云怎么用?腾讯微云网盘上传文件教程.docx
根据《谈婚轮嫁,营销有“数”——腾讯结婚行业洞察白皮书(2021年版)》,我们可以提炼出以下知识点: 1. 婚庆市场现状:近年来中国结婚人口比例持续下降,2020年在疫情影响下,全国上半年结婚登记对数大幅下降。...
标题中的“腾讯云产品图标ICON官方出品”表明这是一份由腾讯云官方发布的关于其产品图标的集合。这些图标可能是用于表示腾讯云的各种服务、工具或解决方案,旨在提供一致且专业的视觉标识,以便用户能够轻松识别和...
国家数字竞争力指数研究报告2019-腾讯研究院-中国人民大学-201906.pdf
腾讯和阿里组织变革的战略升级 在当前快速变化的商业环境中,企业需要不断自我升级和变革,以适应不断变化的市场环境和用户需求。腾讯和阿里这两家中国最大的互联网企业,也在不断地进行组织变革,以保持其竞争优势...
腾讯研究院:PDF 腾讯数字生活报告
小Q今天在上厕所时想到了这个问题:有n个数,两两组成二元组,差最小的有多少对呢?差最大呢? 输入描述: 输入包含多组测试数据。 对于每组测试数据: N - 本组测试数据有n个数 a1,a2...an - 需要计算的数据 ...
腾讯业务产品线众多,拥有海量的活跃用户,每天线上产生的数据超乎想象,必然会成为数据大户,为了保证公司各业务产品能够使用更丰富优质的数据服务,腾讯的大数据平台做了那些工作?具备哪些能力?大数据,这个词...
《腾讯专题:腾讯生态圈如何与金融融合》 随着科技的发展,互联网巨头腾讯在金融服务领域的影响力日益增强。腾讯生态圈,以其庞大的用户基础、多元化的服务场景和先进的技术能力,正在逐步改变金融行业的格局,实现...
### 腾讯C++编码规范解读 #### 1. 概述 腾讯C++编码规范是一套由腾讯集团制定的、旨在规范公司内部C++编程风格的标准文档。该规范首次发布于2007年10月25日,目的在于确保所有使用C和C++语言开发的产品具有统一的...
25 面试腾讯 IEG 平台产品经理,应该做好哪些准备?.md