面试题-在乱序不重复大量数据里面找缺失的数

标签: 面试 乱序 数据 | 发表时间:2012-03-17 23:16 | 作者:yangliuy
出处:http://blog.csdn.net

这是我面试A公司时碰到的算法题,题目大意是一本书缺了一页,然后书页顺序被打乱,问如何迅速找到缺失的那一页?

思路:其实就是在乱序数组里面找缺失的一个数,有以下方法

1、直接排序,然后遍历一次  时间复杂度O(NlogN),不需要额外空间

2、用bitmap思想,开一个大数组,可以用bitset以节省空间,遍历一遍该数组,出现的数字置位为1,遍历完毕后,没有置位的那一位对应的数就是缺失的数字,时间复杂度O(N),但是需要O(N)的额外空间

3、原地桶排序思想,遍历数组,如果脚标与值相等不做任何处理;否则交换该数到其值索引的那个位置,对于被占用位置的数字,采用同样的方法放到其值索引的位置,直到数组末尾,此时只有空缺的那个数为脚标的那个数的值不等于其脚标。复杂度O(N),且没有额外空间,是最佳算法

算法实现如下,以10个数字为例

#include <iostream>
using namespace std;

int main(){
	int a[10] = {3,2,4,9,6,1,0,8,7,-1};
	int temp;
	int temp_val;
	for(int i = 0; i < 10; i++){
		if(a[i] != i){
			temp_val = temp = a[a[i]];//临时变量先存储需要更换的值
			a[a[i]] = a[i];
			a[i] = temp;
			}
		while(a[temp_val] != temp_val){
			temp = a[temp_val];
			a[temp_val] = temp_val;
			temp_val = temp;
			if(temp_val == -1) break;
		}
	}
	for(int j = 0; j < 10; j++){
		cout<<a[j]<<endl;
		if(a[j] != j) cout<<"the miss number is"<<j<<endl;
	}
	return 0;
}

程序可以在O(N)时间内找到缺失的数字5,且不占用额外空间。


作者:yangliuy 发表于2012-3-17 23:16:48 原文链接
阅读:11 评论:0 查看评论

相关 [面试 乱序 数据] 推荐:

面试题-在乱序不重复大量数据里面找缺失的数

- - CSDN博客推荐文章
这是我面试A公司时碰到的算法题,题目大意是一本书缺了一页,然后书页顺序被打乱,问如何迅速找到缺失的那一页. 思路:其实就是在乱序数组里面找缺失的一个数,有以下方法. 1、直接排序,然后遍历一次  时间复杂度O(NlogN),不需要额外空间. 2、用bitmap思想,开一个大数组,可以用bitset以节省空间,遍历一遍该数组,出现的数字置位为1,遍历完毕后,没有置位的那一位对应的数就是缺失的数字,时间复杂度O(N),但是需要O(N)的额外空间.

海量数据面试题整理

- Sam - 中文热文榜|最新
还有 dongliqian, freiz, Haides, 推荐,查看全部 6 个推荐. 博客园-首页原创精华区发表于2010-07-20 15:15:00. 作者: 小橋流水 发表于 2010-07-20 15:15 原文链接 阅读: 415 评论: 3. 给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url.

大数据量的算法面试题

- - 编程 - 编程语言 - ITeye博客
作者:July、youwang、yanxionglu. 时间:二零一一年三月二十六日. 说明:本文分为俩部分,第一部分为10道海量数据处理的面试题,第二部分为10个海量数据处理的方法总结. 出处:http://blog.csdn.net/v_JULY_v. 第一部分、十道海量数据处理面试题. 1、海量日志数据,提取出某日访问百度次数最多的那个IP.

机器学习及大数据相关面试的职责和面试问题

- - IT瘾-bigdata
· 机器学习、大数据相关岗位的职责. 各个企业对这类岗位的命名可能有所不同,比如推荐算法/数据挖掘/自然语言处理/机器学习算法工程师,或简称算法工程师,还有的称为搜索/推荐算法工程师,甚至有的并入后台工程师的范畴,视岗位具体要求而定. 机器学习、大数据相关岗位的职责. 根据业务的不同,岗位职责大概分为:.

转:面试中的海量数据处理问题

- friedvan - 丕子
终于找到了一份比较完整的,分享一下. 海量数据处理:十道面试题与十个海量数据处理方法总结. 作者:July、youwang、yanxionglu. 时间:二零一一年三月二十六日. 说明:本文分为俩部分,第一部分为10道海量数据处理的面试题,第二部分为10个海量数据处理的方法总结. 出处:http://blog.csdn.net/v_JULY_v.

数据科学家面试常见的77个问题

- - 互联网分析
随着大数据概念的火热,数据科学家这一职位应时而出,那么成为数据科学家要满足什么条件. 或许我们可以从国外的数据科学家面试问题中得到一些参考,下面是中国统计网为大家翻译的数据科学家面试常见的77个问题. 下面是77个关于数据分析或者数据科学家招聘的时候会常会的几个问题,供各位同行参考. 1、你处理过的最大的数据量.

面试笔试常考的mysql 数据库操作group by

- - CSDN博客数据库推荐文章
IT 面试中,数据库的相关问题基本上属于必考问题,而其中关于sql语句也是经常考察的一个重要知识点. 下面介绍下sql语句中一个比较重要的操作group by,他的重要行一方面体现在他的理解困难度,一方面体现应用中的长见性. 首先,给出一个studnet学生表:. 给出各个部门最高学生的分数. 要想得到各个部门学生,首先就要分组,按照部门把他们分组,然后在各个部门中找到分数最高的就可以了.

大数据面试可能遇到的问题

- - 数据库 - ITeye博客
1、你处理过的最大的数据量. 2、告诉我二个分析或者计算机科学相关项目. 3、什么是:提升值、关键绩效指标、强壮性、模型按合度、实验设计、2/8原则. 4、什么是:协同过滤、n-grams, map reduce、余弦距离. 5、如何让一个网络爬虫速度更快、抽取更好的信息以及更好总结数据从而得到一干净的数据库.

海量数据处理常见面试题

- - CSDN博客推荐文章
给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url. 方案1:可以估计每个文件安的大小为50G×64=320G,远远大于内存限制的4G. 所以不可能将其完全加载到内存中处理. s 遍历文件a,对每个url求取,然后根据所取得的值将url分别存储到1000个小文件(记为)中.

数据库面试常问的一些基本概念

- - IT瘾-geek
点击上方“Java知音”,选择“置顶公众号”. 链接:https://blog.csdn.net/u013142781. Javaweb练手项目源码下载. 1、超键、候选键、主键、外键. 超键:在关系中能唯一标识元组的属性集称为关系模式的超键. 一个属性可以为作为一个超键,多个属性组合在一起也可以作为一个超键.