二分查找
二分查找是一种高效的查找算法，但是要求我们前提数据必须是有序的。
实现思路：说白了就是和中间的数比较，如果比中间数小，就和左半部分中间数继续比较，如果比中间数大、就和右半部分中间数继续比较，直到找到为止。
循环二分查找
public static int binarySearch(int[] arr, int key) { //定义左指针和右指针 int left = 0; int right = arr.length - 1; //当查找的值比最小的还小、最大的还大，直接退出 if (key < arr[left] || key > arr[right]) { return -1; } //当左指针小于等于右指针一直进行循环 while (left <= right) { //定义中间值 int mid = (left + right) / 2; //如果中间值小于查找当值，那么左指针右移 if (arr[mid] < key) { left = mid + 1; } else if (arr[mid] > key) { right = mid - 1; } else { return mid; } } return -1; }
递归二分查找
public static int binarySearch(int[] a, int key, int left, int right) { //设置递归退出的条件：当查找当值比最小值小，最大值大，或者左指针大于右指针当时候退出 if (key < a[left] || key > a[right] || left > right) return -1; //定义中间值 int mid = (left + right) / 2; //递归搜索 if (a[mid] < key) { return binarySearch(a, key, mid + 1, right); } else if (a[mid] > key) { return binarySearch(a, key, left, mid - 1); } else { return mid; } }
二维矩阵(第74题)
题目要求：
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例1 ：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出：true
示例2 ：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 输出：false
实现思路：
这题我们把二维数组转换为一维数组，然后进行二分查找来做。
找到一维数组下标和二维数组下标的关系是关键
二维数组下标第一位是：一维数组下标/列数
二维数组下标第二位是：一维数组下标%列数
public static boolean searchMatrix(int[][] matrix, int target) { if (matrix.length == 0) { return false; } int row = matrix.length; int col = matrix[0].length; int left = 0; int right = row * col - 1; while (left <= right) { int mid = (left + right) / 2; if (target < matrix[mid / col][mid % col]) { right = mid - 1; } else if (target > matrix[mid / col][mid % col]) { left = mid + 1; } else { return true; } } return false; }
寻找重复数(第287题)
题目要求：给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
示例2：
输入：nums = [1,3,4,2,2] 输出：2
HashMap
public static int findDuplicate(int[] nums) { HashMap<Integer, Integer> map = new HashMap<>(); for (int num : nums) { if (map.containsKey(num)) { return num; } else { map.put(num, 1); } } return -1; }
相邻元素
public static int findDuplicate(int[] nums) { Arrays.sort(nums); for (int i = 0; i < nums.length - 1; i++) { if (nums[i] == nums[i + 1]) { return nums[i]; } } return -1; }
快慢指针(转换为环形链表)
由于以上两种方法很常见，并且效率也是一般，这题我们使用链表的思想解决。
这样的话此题就变成了找环形链表的出口，我们分为两步骤来寻找出口。
步骤一：寻找链表中的环形链表
定义两个指针，分别是快指针和慢指针
指针走两步，慢指针走一步
当快慢指针相遇当时候，必定会在环中
步骤二：寻找环形链表上的入口节点
定义两个指针，让before指向链表最开始，让after指向相交点
当两个指针相遇，那么就是环形链表当入口点
public static int findDuplicate(int[] nums) { int fast = 0; int low = 0; /** * 第一阶段：寻找链表中的环 * 定义两个指针，分别是快指针和慢指针 * 快指针走两步，慢指针走一步 * 当快慢指针相遇当时候，必定会在环中 */ do { low = nums[low]; fast = nums[nums[fast]]; } while (fast != low); /** * 第二阶段：寻找环形链表上的入口节点 * 定义两个指针，让before指向链表最开始，让after指向相交点 * 当两个指针相遇，那么就是环形链表当入口点 */ int before = 0; int after = low; while (before != after) { before = nums[before]; after = nums[after]; } return before; }
