空间换时间案例—最快速度求0-9999顺序打乱中缺失和重复的数和2020年
程序员文章站
2024-01-09 23:26:46
文章目录一、问题二、代码一、问题题目的思想 :拿时间换空间, 拿空间换时间 题: 有一个容器, 里面存储了1万个 连续的数 0-9999 (数的顺序是打乱的) , 但是这些数组里面 其中一个数 是缺失的, 有一个数 是重复的。 比如: 0 1 2 3 7 5 6 7 8 9 -- 7 是重复的 4是缺失的。 顺序乱的: 9 6 7 3 2 7 5 1 0 8 -- 7 是重复的 4是缺失的。 请你 用最快...
一、问题
题目的思想 :拿时间换空间, 拿空间换时间
题: 有一个容器, 里面存储了1万个 连续的数 0-9999 (数的顺序是打乱的) , 但是这些数组里面 其中一个数 是缺失的, 有一个数 是重复的。
比如: 0 1 2 3 7 5 6 7 8 9 -- 7 是重复的 4是缺失的。
顺序乱的: 9 6 7 3 2 7 5 1 0 8 -- 7 是重复的 4是缺失的。
请你 用最快速的方法, 找到 那个缺失的数, 找到那个重复的数。
二、代码
import java.util.*;
public class Demo3 {
public static void main(String[] args) {
Integer[] intArr = getIntArr(10000);
int[] newIntArr = new int[intArr.length];
for (int i = 0; i < intArr.length; i++) {
newIntArr[intArr[i]]++;
}
for (int i = 0; i < newIntArr.length; i++) {
if (newIntArr[i] == 0) {
System.out.println("查找的缺失的值是:" + i);
} else if (newIntArr[i] == 2) {
System.out.println("查找的重复的值是:" + i);
}
}
}
private static Integer[] getIntArr(int len) {
Random r = new Random();
LinkedList<Integer> intList = new LinkedList<>();
for (int i = 0; i < len; i++) {
intList.add(i);
}
int repNum = 0;
int loserNum = 0;
while (true) {
repNum = r.nextInt(len);
loserNum = r.nextInt(len);
if (!(repNum == loserNum)) {
break;
}
}
intList.set(loserNum, repNum);
System.out.println("生成的缺失数是:" + loserNum);
System.out.println("生成的重复数是:" + repNum);
Collections.shuffle(intList);
Integer[] intArr = intList.toArray(new Integer[intList.size()]);
return intArr;
}
}
生成的缺失数是:4951
生成的重复数是:4466
查找的重复的值是:4466
查找的缺失的值是:4951
本文地址:https://blog.csdn.net/weixin_46006988/article/details/110295892
上一篇: PHP实现查找表