JZ3 数组中重复的数字

题目难度：简单

题目描述：

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1

数据范围：0≤n≤10000

进阶：时间复杂度O(n) ，空间复杂度O(n)

示例一：

输入：[2,3,1,0,2,5,3]
返回值：2
说明：2或3都是对的

思路一 ：暴力枚举

时间复杂度：O(n^2)

class Solution {
  int duplicate(vector<int>& numbers) {
      // 边界判断
      if (numbers.size() < 1) return -1;

      int res = -1, nSize = numbers.size();
      for (int i = 1; i < nSize(); i++) {
          int temp = numbers[i];
          for (int j = i + 1; j < nSize(); j++) {
              if (temp == numbers[j]) {
                  res = temp;
                  break;
              }
          }
      }
      return res;
  }
}

运行时间：

思路二：排序

时间复杂度：O(nlogn)

calss Solution {
  int duplicate(vector<int>& numbers) {
      if (numbers.size() < 1) return -1;

      sort(numbers.begin(), numbers.end());  // O(nlogn)

      int res = -1;
      int nSize = numbers.size();
      for (int i = 0; i < nSize - 1; i++) {
          if (numbers[i] == numbers[i+1]) {
              res = numbers[i];
              break;
          }
      }
      return res;
  }
}

运行时间：

思路三：哈希表

时间复杂度：O(n)

class Solution {
  int duplicate(vector<int>& numbers) {
      if (numbers.size() < 1) return -1;
      vector<int> hashmap(numbers.size(), 0);

      for (int i = 0; i < numbers.size(); i++) {
          hashmap[numbers[i]]++;
          if (hashmap[numbers[i]] > 1) return numbers[i];
      }
      return -1;
  }
}

运行时间：