剑指 Offer —— 数组中重复的数字

释放双眼,带上耳机,听听看~!

数组中的重复数字

题目描述

牛课网链接

长度为 n 的数组里,所有数字都在 0 到 n-1 的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为 7 的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字 2 或者 3。(牛课网这里弄成「那么对应的输出是第一个重复的数字 2」了)

A 简单实现思路

借助外部数组 b,原数组中的数字记为外部数组的下标,外部数组的值来存储这个数字出现的次数。原数组中的数字都在 0 到 n-1 的范围内,因此外部数组 b 的长度为 n 即可。

public boolean duplicate(int[] numbers, int length, int[] duplication) {
        if (numbers == null) {
            return false;
        }
        
        int[] array = new int[length];
        for (int i = 0; i < length; i++) {
            if (array[numbers[i]] > 0) {
                duplication[0] = numbers[i];
                return true;
            }
            array[numbers[i]]++;
        }
        return false;
}

时间复杂度 O(n),空间复杂度 O(n)

B 剑指 Offer 思路

如果数组中没有重复的数字,排序后第 i 个位置会存放值为 i 的数字。因为数组中某些数字是重复的,在排序后,某个位置处会存放多个相同数字(逻辑上的,就相当于叠起来),有些位置就没有数字。前者就是我们要找的数字。但是我们并不去排序,只是利用这种思想,把值为 i 的元素放到下标为 i 的位置。

具体来说,我们从前往后依次遍历该数组。当遍历到下标 i 时,记该位置上的数字为 x,如果 x 等于 i,就跳过。如果 x 不等于 i,就判断 x 应放位置处(即下标 x 处)的数字(计作 m)是否已经是 x 了,如果是就找到了一个重复的数字(循环结束);如果 m 不等于 x,那么就交换下标 i、x 的两个数(保证把位置 i 处的 x 放置到正确的位置上),直到 x 等于 i。

/**
 * 将值为 i 的元素调整到下标为 i 的位置,如果该位置上的数已经等于 i 了,就说明 i 已经重复了
 * @param numbers
 * @param length
 * @param duplication
 * @return
 */
public static boolean jz(int[] numbers, int length, int[] duplication) {
    for (int i = 0; i < length; i++) {
        //下标 i 处的数 numbers[i],若不与下标 i 相等,就把 numbers[i] 放到下标 numbers[i] 处
        while (numbers[i] != i) {
            //在交换位置之前还要检查下标 numbers[i] 处的数字是否已经是 numbers[i],如果是就已经找到了重复的数字
            if (numbers[numbers[i]] == numbers[i]) {
                duplication[0] = numbers[i];
                //注意这里不是 break
                return true;
            }

            //交换下标为 i、numbers[i] 两个位置上的数字(保证值为 numbers[i] 的元素放到下标 numbers[i] 处)
            swap(numbers, i, numbers[i]);
        }
    }
    return false;
}

/**
 * 交换下标为 i、j 的两个数
 * @param numbers
 * @param i
 * @param j
 */
public static void swap(int[] numbers, int i, int j) {
    int swap = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = swap;
}

给TA打赏
共{{data.count}}人
人已打赏
随笔日记

nginx分布式实例入门操作

2020-11-9 4:42:26

随笔日记

Spring-Security-Oauth2.0浏览器端的登录项目分享

2020-11-9 4:42:28

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索