欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

空间换时间案例—最快速度求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