Hongwei's Diary
Fork me on GitHub

数组中重复的数字

2017-04-02

一、问题描述

在长度为n的数组中，所有的元素都是0到n-1的范围内。 数组中的某些数字是重复的，但不知道有几个重复的数字，也不知道重复了几次，请找出任意重复的数字。 例如，输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出为2或3

解法一：排序扫描

将输入的数组进行排序，遍历排序后的数组找到重复的数字。排序一个长度为n的数字的时间复杂度为$\omicron(nlogn)$,所以这种方法的时间复杂度为$\omicron(nlogn)$。

解法二：使用哈希表

使用哈希表来解决这个问题。从头到尾顺序扫描数组中的每一个数，没扫描一个数字可以用$\omicron(1)$的时间在哈希表中判断是否包含此数字，如果哈希表中没有此数字就将此数字加入到哈希表中，如果哈希表中已存在此数字就找到重复的数字。时间复杂度为$\omicron(n)$，但是空间复杂度也为$\omicron(n)$，以空间换区时间。

解法三：比较交换

数组中的数字为0到n-1的范围内。如果这个数组中没有重复的数字，则对应的i位置的数据也为i。可以重排此数组，扫描数组中的每个数字，当扫描到下标为i的数字时，首先比较这个数字（m）是不是等于i。如果是，接着扫描下一个数字。如果不是，再拿它和第m个数字比较，如果相等则找到重复的数据。否则就把第i个数字与第m个数字交换。重复这个比较、交换的过程，直到找到重复的数字。

代码中尽管有一个两重循环，但每个数字最多只要交换两次就能找到属于它自己的位置，因此总的复杂度是$\omicron(n)$，另外所有的操作都是在输入数组上进行的，不需要额外的分配内存，空间复杂度为$\omicron(1)$

public class DuplicateNumber {

    public static void main(String[] args) {
        int[] numbers = {2, 3, 1, 0, 2, 5, 3};
        int[] duplication = new int[1];
        boolean bool = duplicate(numbers, numbers.length, duplication);
        if (bool) {
            System.out.println(duplication[0]);
        } else {
            System.out.println("数组中无重复数字！");
        }
    }

    private static boolean duplicate(int[] numbers, int length, int[] duplication) {
        if (numbers == null || length <= 0)
            return false;
        for (int a : numbers) {
            if (a < 0 || a >= length)
                return false;
        }

        int temp;
        for (int i = 0; i < length; i++) {
            while (numbers[i] != i) {
                if (numbers[numbers[i]] == numbers[i]) {
                    duplication[0] = numbers[i];
                    return true;
                }
                temp = numbers[i];
                numbers[i] = numbers[temp];
                numbers[temp] = temp;
            }
        }
        return false;
    }
}
Tags: 剑指offer
← Java Socket编程【转】 Oracle CLOB 笔记 →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏

扫描二维码，分享此文章