package com.myway.study;
import java.util.ArrayList;
import java.util.List;
/**
* 给出一个顺序文件,它最多包含40亿个随机排列的32位整数
问题:找出一个不在文件中的32位整数。
* User: zhangyong
* Date: 14-5-17
* Time: 下午12:38
* To change this template use File | Settings | File Templates.
*/
public class BinarySearchNoExist {
public static Integer lostNum(int arr[], int len, int maxBits) {
List lostNumList = new ArrayList();
int lostNum = 0;
int MASK = 0;
int locZero = 0;
int locOne = 0;
int[] arrZero = new int[len];
int[] arrOne = new int[len];
for (int bit = maxBits - 1; bit >= 0; bit--) {
locOne = 0;
locZero = 0;
MASK = 1 << bit;
for (int i = 0; i < len; i++) {
if ((arr[i] & MASK) == MASK) {
arrOne[locOne++] = arr[i];
} else {
arrZero[locZero++] = arr[i];
}
}
if ((locOne == MASK) && (locZero == MASK)) {
} else {
if (locOne > locZero) {
arr = arrZero;
len = locZero;
} else {
lostNum += MASK;
arr = arrOne;
len = locOne;
}
}
}
return lostNum;
}
public static void main(String[] args) {
int[] arr = {4, 2, 3, 5, 7, 10, 9, 11, 12, 14};
System.out.println(lostNum(arr, arr.length, 4));
}
}
分享到:
相关推荐
32位无符号整数的范围是0 ~ 4 294 967 295,现在有一个正好包含40亿个无符号整数的文件,所以在整个范围中必然有未出现过的数。怎么找到所有未出现过的数? 要求: 可以使用最多1GB的内存。 进阶: 内存限制10MB,...
1.提取出某日访问百度次数最多的那个IP 2.有一个1G大小的一个文件,里面每一行是...5.腾讯面试题:给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中? ......
(29)某公司在传输数据过程中为了安全要对数据进行加密,若传递的是四位的整数,对其进行加密的规则为:每位数字都加上5,然后用和除以10的余数代替该数字,再将第一位和第四位交换,第二位和第三位交换。...
7.8找出一个二维数组中的鞍点,即该位置上的元素在该行上最大,在该列上最小。也可能没有鞍点。 38 7.9有15个数按从小到大的顺序存放在一个数组中。输入一个数,要求用折半查找法找出该数是数组中第几个元素的值。...
32位无符号整数的范围是0 ~ 4 294 967 295 现在有40亿个无符号整数,可以使用最多1GB的内存,找出所有出现了两次的数。 补充问题: 可以使用最多10MB的内存,怎么找到40亿个整数的中位数? 原问题: 可以用 bit map ...
-n:一般而言,mount挂上后会在/etc/mtab中写入一笔资料,在系统中没有可写入文件系统的情况下,可以用这个选项取消这个动作。 4.应用技巧 在Linux 和Unix系统上,所有文件都是作为一个大型树(以/为根)的一部分...
2、某系的成绩登记册中,每个班最多有40个学生,每份成绩表中的成绩信息包括:学号(9位字符),姓名(8位字符),成绩(百分制),备注(20位字符)。设计程序以处理一个班的成绩信息,包括输入、输出、查询(给定...
12、 已知一个顺序表中的元素按元素值非递减有序排列,编写一个函数删除表中多余的值相同的元素。 13、 分别写出求二叉树结点总数及叶子总数的算法。 分治术 14、 有金币15枚,已知其中有一枚是假的,而且它的重量...
利用Java编写程序从键盘输入一个整数,计算并输出该数的数字之和。例如:请输入一个整数:8899123各位数字之和为:40
要求编程建立一个文本文件,每个单词不包含空格且不跨行,单词由字符序列构成且区分大小写;统计给定单词在文本文件中出现的总次数;检索输出某个单词出现在文本中的行号、在该行中出现的次数以及位置。 该设计要求...
以汉字“啊”为例,它的区号为16,位号为1,故它的32字节字形信息在文件中的起始字节偏移量offset=((区号-1)*94+位号-1)*32。 0000010010000000 0x04,0x80 0000111010100000 0x0E,0xA0 0111100010010000 0x78,0x90 ...
在Skylake Intel处理器上,它可以0.3个周期/整数的速率解码整数,可以轻松地将其转换为每秒8个以上的十亿个整数。 该库是C资源的列表的一部分。 贡献者:Daniel Lemire,Nathan Kurz,Christoph Rupp,Anatol ...
实现1~40为的整数(超过int、long等类型的范围)的加减乘除
第十三章 文件 对数据的管理无论是用数组还是链表,都是存储在内存中的,程序结束后都会丢失,下一次运行程序时,要重新输入或运算生成数据。要把程序运行的数据保存起来以便下次运行继续使用,在计算机中持久保存...
0086 用回溯法找出n个自然数中取r个数的所有组合 58 0087 0~N位数的任意组合 59 0088 在数组中快速查找近似值 60 0089 实现直接插入法排序 61 第4章 函数应用 63 4.1 字符串处理函数 64 0090 使用...
RAR 是一个让你在命令行模式中管理压缩文件的控制台应用。RAR 提供压缩、加 密、数据恢复和许多其它此手册中描述的其它功能。 RAR 只支持 RAR 格式压缩文件,它默认有 .rar 扩展名。不支持ZIP 和其他格 式。即使...
举个例子,在10-20之间随机输出一个整数,则 var lanrenzhijia = Math.floor(Math.random()*(20-10)+ 10); alert(lanrenzhijia); 预览页面为随机生成10-20之间的任意整数
很多家庭都有温湿度计,它实际上是通过大气温度传感器来获取温度和湿度信息,并显示在表盘中的。而我们要做的程序就是模拟这个过程,生成天气数据,然后显示出来。 需求分析: 1、设计一个天气类Weather,用于温度...
Java生成一个文件打开的文件选择对话框窗口,和Win系统的浏览文件窗口相似,使用Java代码模拟实现的窗口程序,相关代码如下: button.addActionListener(new ActionListener() { //按钮事件处理 public void ...
LeetCode问题12是关于“整数转罗马数字”的问题,它要求将一个整数转换为罗马数字表示。罗马数字使用七个不同的符号表示不同的值:I(1)、V(5)、X(10)、L(50)、C(100)、D(500)和M(1000)。为了表示其他...