剑指offer-03-数组中重复的数字

题目描述

找出数组中重复的数字。

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

示例1：

1
2
3

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

需要考虑到时间复杂度和空间复杂度的要求

如果要求时间复杂度，可以考虑用hash table.(时间复杂度 O(N) 空间复杂度 O(N))

如果要求空间复杂度，可以先排序，再看前后有无重复数字.(时间复杂度 O(Nlog(N)) 空间复杂度 O(1))

如果都有要求，考虑原地置换法 .(时间复杂度 O(N) 空间复杂度 O(1))

算法

leetcode hash-table 剑指offer

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！