Contains Duplicate

描述

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

分析

方法1， 用一个 HashSet, 不断往里面塞元素，如果发现有重复，说明存在重复。时间复杂度O(n)，空间复杂度O(n)。

方法2， 排序，然后从头到尾扫描，如果发现相邻两个元素相等，则存在重复。时间复杂度O(nlogn)，空间复杂度O(1)。

解法1 哈希表

  1. // Contains Duplicate
  2. // Time Complexity: O(n), Space Complexity: O(n)
  3. public class Solution {
  4.     public boolean containsDuplicate(int[] nums) {
  5.         final Set<Integer> existed = new HashSet<>();
  6.         for (int x : nums) {
  7.             if (existed.contains(x)) {
  8.                 return true;
  9.             } else {
  10.                 existed.add(x);
  11.             }
  12.         }
  13.         return false;
  14.     }
  15. }

解法2 排序

  1. // Contains Duplicate
  2. // Time Complexity: O(nlogn), Space Complexity: O(1)
  3. public class Solution {
  4.     public boolean containsDuplicate(int[] nums) {
  5.         Arrays.sort(nums);
  7.         for (int i = 1; i < nums.length; ++i) {
  8.             if (nums[i-1] == nums[i]) return true;
  9.         }
  10.         return false;
  11.     }
  12. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/linear-list/array/contains-duplicate.html