[每日一题] 第十九题:数组中重复的数字

题目描述

找出数组中重复的数字。

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

示例 1:

输入:

[2, 3, 1, 0, 2, 5, 3]
输出:23 

限制:

  • 2 <= n <= 100000

题解

方法一:我的做法

还可以优化,但是这毕竟是我提交的,所以直接复制粘贴。哈哈。

代码

class Solution {
    public int findRepeatNumber(int[] nums) {
        int length = nums.length;
        int[] index = new int[length];
        for (int i=0; i<length; i++) {
            index[i] = 0;
        }
        for (int i=0; i<length; i++) {
            index[nums[i]]++;
        }
        for(int i=0; i<length; i++) {
            if (index[i] > 1) {
                return i;
            }
        }
        return 0;
    }
}

复杂度

时间复杂度:O(3N)
空间复杂度:O(N)

方法二:使用集合遍历数组

由于只需要找出数组中任意一个重复的数字,因此遍历数组,遇到重复的数字即返回。为了判断一个数字是否重复遇到,使用集合存储已经遇到的数字,如果遇到的一个数字已经在集合中,则当前的数字是重复数字。

初始化集合为空集合,重复的数字 repeat = -1
遍历数组中的每个元素:
将该元素加入集合中,判断是否添加成功
如果添加失败,说明该元素已经在集合中,因此该元素是重复元素,将该元素的值赋给 repeat,并结束遍历
返回 repeat

代码

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        int repeat = -1;
        for (int num : nums) {
            if (!set.add(num)) {
                repeat = num;
                break;
            }
        }
        return repeat;
    }
}

复杂度

时间复杂度:O(n)。
遍历数组一遍。使用哈希集合(HashSet),添加元素的时间复杂度为 O(1),故总的时间复杂度是 O(n)。
空间复杂度:O(n)。不重复的每个元素都可能存入集合,因此占用 O(n) 额外空间。

个人理解

  1. 集合特性: 集合类中的 Set.add() 方法用来向 Set 集合添加对象。如果 Set 集合中已经包含相同的对象,则不改变 Set 集合。该方法返回值为 boolean 对象,如果 Set 集合中不包含要添加的对象,则添加对象并返回 true,否则返回 false

来源

作者:LeetCode-Solution
链接:leetcode-cn.com/problems/shu-zu-zh...
来源:力扣(LeetCode)

来源

来源:力扣(LeetCode)
链接:leetcode-cn.com/problems/shu-zu-zh...
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!