题解 | #数组中重复的数字#

数组中重复的数字

http://www.nowcoder.com/practice/6fe361ede7e54db1b84adc81d09d8524

这道题的关键在于时间复杂度要求为O(n),因此如果采用每一个元素都遍历一遍数组的话,时间复杂都就成了O(n^2)。 因此我们需要另辟蹊径,让数组中的每个元素都有一个状态(为 0 为没有遍历过,为 1 则为已被遍历过)。由于 0 <= n <= 10000,所以需要 new 一个大小为 10000 的整型数组 array 。当一个数 nums[ i ] 被遍历到时,将会把 array[ nums[ i ] ] 的值置为 1 来表示这个数已被遍历过一次了,当再次遍历到 nums[ i ] 时,就说明重复了,直接把值放回。这样时间复杂度就下降到了 O(n)。

	public int duplicate (int[] numbers) {
        int[] array = new int[10000];
        for (int i = 0; i < numbers.length; i++) {
            if (array[numbers[i]] == 0) {
                array[numbers[i]] = 1;
            }else {
                return numbers[i];
            }
        }
        return -1;
    }
全部评论

相关推荐

不愿透露姓名的神秘牛友
10-25 11:34
大飞的诡术妖姬:看岔了,还以为这公司要避雷,没绷住
点赞 评论 收藏
分享
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务