找出一个数组中重复的数字,数组长度为 n, 数字都在 0-n-1 范围内。
[2, 3, 1, 0, 2, 5, 3]
[2, 3]
先排序,然后遍历,每次遍历时记录上一个数字,然后当前数字如果等于上一个数字,就返回。 排序时间复杂度 O(nlogn), 遍历时间复杂度 O(n),总耗时 O(nlogn)。
用一个数组来记录已经出现的数字,然后遍历时如果已经在数组中,那就判定为重复。 时间复杂度为 O(n),空间复杂度为 O(n)。
思考数组的特点,长度为 n,范围是 0-n-1,那么排序完了之后必然是 0-n-1。
所以,可以进行遍历,当遍历到下标为 i 的数字时,假设当前数字为 m,看 m 是不是等于 i,如果 不是,再判断这个数字 m 是不是和下标为 m 的数字相等,如果相等,那就是重复的,将这个数字返回, 如果不相等,那么将 m 和下标为 m 的数字交换位置。然后循环往复扫描下一个数字。
时间复杂度为 O(n),空间复杂度为 O(1)。