Leetcode 704 二分查找

leetcode 链接
https://leetcode-cn.com/problems/binary-search/
​
​
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
 
​
示例 1：
​
输入：nums = [1,2,3,1]
输出：true
示例 2：
​
输入：nums = [1,2,3,4]
输出：false
示例 3：
​
输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true
​
​
提示：
​
1 <= nums.length <= 105
-109 <= nums[i] <= 109

由提示可知，该题会添加时间限制。

第一种解法：将元素排好序后，相等元素会紧邻，因此我们扫描数组即可得到答案

Java 版本

public  boolean containsDuplicate(int[] nums) {
      Arrays.sort(nums);
       for (int i = 0; i < nums.length - 1; i++) {
           if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
     return false;
}

golang版本

func containsDuplicate(nums []int) bool {
  sort.Ints(nums)
  for i := 0; i < len(nums)-1; i++ {
    if nums[i] == nums[i+1] {
      return true
    }
  }
  return false
}

复杂度分析
​
时间复杂度：O(NlogN)，其中 N 为数组的长度。需要对数组进行排序。
​
空间复杂度：O(logN)，其中 N 为数组的长度。注意我们在这里应当考虑递归调用栈的深度。
​

第二种解法：哈希表，相同元素会碰撞到一起，由此判断是否有元素相等

Java版本

    public  boolean containsDuplicate(int[] nums) {
        Set set = new HashSet<>();
        for (int x : nums) {
            if (!set.add(x)) {
                return true;
            }
        }
        return false;
    }

golang版本

func containsDuplicate(nums []int) bool {
  set := map[int]struct{}{}
  for _, v := range nums {
    if _, has := set[v]; has {
      return true
    }
    set[v] = struct{}{}
  }
  return false
}

复杂度分析
时间复杂度：O(N)，其中 N 为数组的长度。
空间复杂度：O(N)，其中 N 为数组的长度。