题目地址(03. 数组中重复的数字)

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

题目描述

  1. 找出数组中重复的数字。
  4. 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
  6. 示例 1：
  8. 输入：
  9. [2, 3, 1, 0, 2, 5, 3]
  10. 输出：2 或 3 
  15. 限制：
  17. 2 <= n <= 100000

前置知识


公司

  • 暂无

思路

先排序 然后判断相邻的两个数是否相等 相等直接返回 时间复杂度为nlogN 因为排序需要这个复杂度
还可以使用hash表 理论上时间复杂度为n 但是不知道为什么比上面还慢
第三种最优解 可以根据题意 如果没有重复的数据应该是 数组的下标和数字是一一对应的 如果有数字和索引对应不上的就交换并判断是不是重复了

关键点


代码

  • 语言支持：Java

Java Code:

  2. class Solution {
  3.         public int findRepeatNumber(int[] nums) {
  4.             Arrays.sort(nums);
  5.             for (int i = 0; i < nums.length; i++) {
  6.                 if (nums[i] == nums[i + 1]) {
  7.                     return nums[i];
  8.                 }
  9.             }
  10.             return 0;
  11.         }
  12.     }
  1. class Solution {
  2.         public int findRepeatNumber(int[] nums) {
  3.             HashSet<Integer> set = new HashSet<>();
  4.             for (int i = 0; i < nums.length; i++) {
  5.                 if (set.contains(nums[i])) {
  6.                     return nums[i];
  7.                 }
  8.                 set.add(nums[i]);
  9.             }
  10.             return -1;
  11.         }
  12.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：剑指 Offer 03. 数组中重复的数字 - 图1#card=math&code=O%28n%29&id=IiNbu)
  • 空间复杂度：剑指 Offer 03. 数组中重复的数字 - 图2#card=math&code=O%28n%29&id=PuajQ)