01-数组中重复的数字

原题链接

哈希表法

思路

  1. 初始化集合为空集合
  2. 遍历数组中每一个元素，将元素添加到集合中
  3. 如果添加成功就继续，否则添加失败说明集合中已经有该元素，那么说明重复了

Java实现

  1. import java.util.*;
  2. public class Solution {
  3.     //hash
  4.     public int duplicate (int[] numbers) {
  5.         // write code here
  6.         Set<Integer> set=new HashSet<>();
  7.         int res=-1;
  8.         for(int num:numbers){
  9.             if(!set.add(num)){
  10.                 res=num;
  11.                 break;
  12.             }
  13.         }
  14.         return res;
  15.     }
  16. }

Python实现

  1. class Solution(object):
  2.     def findRepeatNumber(self, nums):
  3.         s=set()
  4.         for num in nums:
  5.             if num not in s:
  6.                 s.add(num)
  7.             else:
  8.                 return num
  9.         return -1
  • 时间复杂度：遍历数组O(n),添加到HashSet的时间复杂度O(1)
  • 空间复杂度：HashSet占用O(n)的空间复杂度

02-二维数组中查找

原题链接
思路
剑指offer - 图1

  • 从二维数组的右上角看，可以看到它左侧的元素比它小，右侧的元素比它大
  • 因此类似于一棵二叉搜索树，满足左小右大的需求
  • 那么我们能否能通过二分的思想将搜索的时间复杂度降到O(logN)呢？

Java实现