2021-06-22-二分法题型（LeetCode）

2021-06-22-二分法题型（LeetCode）

二分法题型

​​LeetCode 35 搜索插入位置​​​​LeetCode 744 寻找比目标字母大的最小字母​​​​LeetCode 153 旋转数组找最小​​​​LeetCode 154 （重复）旋转数组找最小​​​​LeetCode 33 旋转数组找target​​​​LeetCode 81 （重复）旋转数组找target​​​​LeetCode 744 寻找比目标字母大的最小字母​​​​LeetCode 34 在排序数组中查找元素的第一个和最后一个位置​​​​LeetCode 540 有序数组中的单一元素​​​​LeetCode 378 有序矩阵中第 K 小的元素​​

LeetCode 35 搜索插入位置

题目：将target插入值有序数组，使得插入后依然有序思路：二分法，主要注意边界问题代码：

public int searchInsert(int[] nums, int target) { if (nums.length==0||nums==null) return 0; int left =0; int right = nums.length-1; int mid =0; while (left<=right){ mid=(left+right)/2; if (nums[mid]>=target){ right=mid-1; }else { left=mid+1; } } return left; }

LeetCode 744 寻找比目标字母大的最小字母

题目：寻找一个比target大的最小字母。另一种说法：target插入原字符串，使得插入后的字符串依然有序，那么该target后一位就是最小字母，同理前一位就是小于target的最大字母。思路：类比LeetCode 35 ，查找插入位置代码：

public char nextGreatestLetter(char[] letters, char target) { int left =0; int right =letters.length-1; int mid =0; while (left<=right){ mid=left+(right-left)/2; if (letters[mid]>target){ right=mid-1; }else { left=mid+1; } } if (left==letters.length){ return letters[0]; } if (letters[left]==target){ if (left+1==letters.length){ return letters[0]; }else { return letters[left+1]; } }else { return letters[left]; } }

LeetCode 153 旋转数组找最小

题目：有序旋转数组中的最小值（无重复元素）思路：二分法，注意边界代码：

public int findMin(int[] nums) { int left =0; int right =nums.length-1; int mid =0; while (left

LeetCode 154 （重复）旋转数组找最小

题目：有序旋转数组中的最小值（无重复元素）思路：二分法，注意边界代码：

public int findMin(int[] nums) { int left=0; int right=nums.length-1; int mid=0; while (leftnums[right]){ left=mid+1; }else { right--;//明白这一步是为什么 } } return nums[left]; }

LeetCode 33 旋转数组找target

题目：有序数组旋转，寻找target思路：二分法，其实是查找的过程代码：

public int search(int[] nums, int target) { if (nums==null||nums.length==0) return 0; int left =0; int right = nums.length-1; int mid =0; while (left<=right){ mid = left+(right-left)/2; if (nums[mid]==target){ return mid; } if (nums[mid]

LeetCode 81 （重复）旋转数组找target

题目：非递减数组旋转，寻找target思路：二分法，类比LeetCode 154方法代码：

public boolean search(int[] nums, int target) { if (nums==null||nums.length==0) return false; int left =0; int right=nums.length-1; while (left<=right){ int mid = left+(right-left)/2; if (nums[mid]==target){ return true; } if (nums[mid]==nums[right]){ right--; } else if (nums[mid]

LeetCode 744 寻找比目标字母大的最小字母

题目：寻找第一个比目标字母大的字母思路：边界条件是：小于等于target时，left+1。注意right =letters.length;的含义，就是为了让left有机会等于letters.length代码：

public char nextGreatestLetter(char[] letters, char target) { int left =0; int right =letters.length; int mid =0; while (left

LeetCode 34 在排序数组中查找元素的第一个和最后一个位置

题目： 查找元素在数组中的第一个位置和最后一个位置思路：首先定位出target最左端的元素，然后通过定位，等于target+1或者大于target+1的第一个元素的位置。所以此题和LeetCode 744 的区别在于，744 仅仅寻找首个比target大的元素，而此题主要是定位首个大于或者等于target的位置。这里有元素和位置的差异。代码：

public int[] searchRange(int[] nums, int target) { int first = findFirst(nums,target); int last = findFirst(nums,target+1)-1; if (first==nums.length||nums[first]!=target){ return new int[]{-1,-1}; }else { return new int[]{first,last}; } } private int findFirst(int[] nums, int target) { int left = 0; int right = nums.length ; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] >= target) { right = mid; } else { left = mid + 1; } } return left; }

LeetCode 540 有序数组中的单一元素

题目：非递减有序数组，仅仅有一个单一元素，求出次元素的下标思路：有序，指定使用二分，但是如何确定边界？代码：

public int singleNonDuplicate(int[] nums) { int left =0; int right =nums.length-1; while (left

LeetCode 378 有序矩阵中第 K 小的元素

题目 ：有序矩阵（每行没列均升序）中第K个小的元素思路：通过最大值和最小值取平均值，进行二分，然后遍历矩阵，确定left 和right的边界代码：

public int kthSmallest(int[][] matrix, int k) { if (matrix==null||matrix[0].length==0) return 0; int m=matrix.length-1; int n=matrix[0].length-1; int left =matrix[0][0]; int right = matrix[m][n]; while (left

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。