今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题03. 数组中重复的数字

题目链接:https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

一、题目描述

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1:

输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3 

限制:

2 <= n <= 100000

二、题目解析

注意题目描述:一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的 范围 内,这个 范围 恰好与数组的下标可以一一对应。

所以我们可以执行某种操作,使索引与值一一对应即索引 0 的值为 0,索引 1 的值为 1。而一旦某个索引的值不只一个,则找到了重复的数字,也即发生了 哈希冲突

三、动画描述

四、图片描述

面试题03. 数组中重复的数字.002

面试题03. 数组中重复的数字.003

面试题03. 数组中重复的数字.004

面试题03. 数组中重复的数字.005

面试题03. 数组中重复的数字.006

面试题03. 数组中重复的数字.007

面试题03. 数组中重复的数字.008

面试题03. 数组中重复的数字.009

面试题03. 数组中重复的数字.010

面试题03. 数组中重复的数字.011

面试题03. 数组中重复的数字.012

面试题03. 数组中重复的数字.013

面试题03. 数组中重复的数字.014

面试题03. 数组中重复的数字.015

面试题03. 数组中重复的数字.016

面试题03. 数组中重复的数字.017

面试题03. 数组中重复的数字.018

面试题03. 数组中重复的数字.019

面试题03. 数组中重复的数字.020

面试题03. 数组中重复的数字.021

面试题03. 数组中重复的数字.022

面试题03. 数组中重复的数字.023

面试题03. 数组中重复的数字.024

面试题03. 数组中重复的数字.025

面试题03. 数组中重复的数字.026

面试题03. 数组中重复的数字.027

面试题03. 数组中重复的数字.028

面试题03. 数组中重复的数字.029

面试题03. 数组中重复的数字.030

五、参考代码

class Solution {
    public int findRepeatNumber(int[] nums) {
        //设索引初始值为 i = 0
        int i = 0;
        //遍历整个数组 nums 
        while(i < nums.length) {
            //索引 i 的值为 i,无需执行交换操作,查看下一位
            if(nums[i] == i) {
                i++;
                continue;
            }
            //索引 nums[i] 处的值也为 nums[i],即找到一组相同值,返回 nums[i] 即可
            if(nums[nums[i]] == nums[i]) return nums[i];
            //执行交换操作,目的是为了使索引与值一一对应,即索引 0 的值为 0,索引 1 的值为 1
            int tmp = nums[i];
            nums[i] = nums[tmp];
            nums[tmp] = tmp;
        }
        //如果遍历整个数组都没有找到相同的值,返回 -1
        return -1;
    }
}

六、复杂度分析

时间复杂度

遍历数组需要 O(N) 时间。

注意参考代码里面的关键字 continue,这表示在 while 的一次循环里面,只有这次循环将 索引(i)索引值(num[i]) 匹配到了,才会执行下一次循环。

在每一次的循环过程中,索引(i)索引值(num[i]) 匹配到后,在后续的循环过程中不会操作它们,所以虽然一开始的循环过程中,执行的交换操作较多,但在后续的循环过程中根本不需要再执行操作了。

根据均摊复杂度分析 ,总的时间复杂度为 O(N) ,N 为数组的长度。

空间复杂度

使用常数复杂度的额外空间,为 O(1)

七、相关标签

  • 数组
  • 哈希
  • 原地哈希

发表评论

邮箱地址不会被公开。 必填项已用*标注