剑指offer No.3 寻找数组中的重复数字

剑指offer60天计划

Posted by liuwenzi on June 20, 2020
阅读数:

题目:找出数组中重复的数字。

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

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

题解

  • 1.先将数组排序,然后扫描数组,比较数组中相邻数字是否相同。
    • 时间复杂度:O(nlongn)
    • 空间复杂度:O(1)
  • 2.使用hashmap记录数字是否出现,若出现过,则返回此数
    • 时间复杂度:O(n)
    • 空间复杂度:O(n)
  • 3.扫描数组,由于数组长度为n,并且所有数组都在0~n-1的范围内,所以当一个数组下表存储多个元素就是重复的数。

    算法详细步骤:比较数组每一个位置的下标与数组中的值(计为m),如果不相等,则将此数与数组下标为m的元素交换,如数组下标m的元素和m相等,则说明出现重复元素m,退出。若相同,则直接跳过。如果

    • 时间复杂度:O(n) 每个元素最多比较两次
    • 空间复杂度:O(1)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    
    class Solution {
        public int findRepeatNumber(int[] nums) {
            for(int i = 0; i < nums.length; i++){
                int now = nums[i];
                if(now==i){
                    continue;
                }
                if(nums[now]==now){
                    return now;
                }else{
                    int temp = nums[now];
                    nums[now] = now;
                    nums[i] = temp;
                    i--;
                }
            }
            return 0;
        }
    }