怎么快速找出缺失数字

Mocos 发布于 2015/10/30 15:18
阅读 425
收藏 1
假设是0~1W的数字,但是中间随机抽走了几百位,怎样快速准确找出缺失的是哪些数字?
加载中
1
纠结名字
难道不应该是位图法?
0
凉粉
凉粉

目前想到的方法:

1.两个数组减去交集。

2.先把数据放入字典中,然后循环1-1万。挨着判断

3.循环当前数组,判断当前值-1 是不是等于上一个值,如果是则表示连续,如果不是则当前数到上一个数中间数字缺失。如12-19,19-1 != 12 则表示12-19中间数缺失

0
vidy_tu
vidy_tu
二分查找
0
W
William-T
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class Test {
	public static void main(String[] args) {
		//list中有0-10000
		List<Integer> list=new ArrayList<Integer>();
		for (int i = 0; i <=10000; i++) {
			list.add(i);
		}
		Set<Integer> set=new HashSet<Integer>();
		set.addAll(list);
		//随机删除200个
		for (int i = 0; i < 200; i++) {
			int num=(int)(Math.random()*10000);
			System.out.println(num);
			if(list.contains(num)){
				list.remove((Integer)num);
			}
		}
		
		List<Integer> list2=new LinkedList<Integer>();
		
		set.removeAll(list);
		list2.addAll(set);
		System.out.println(list2);
	}
}



返回顶部
顶部