同ip网站做友链,免费网站自动跳转,公司网站建设对公司的重要性,优化方案模板1. 有序数组中的单一元素#xff08;540#xff09;
题目描述#xff1a; 算法原理#xff1a; 二分查找解题关键就在于去找到数组的二段性#xff0c;这里数组的二段性是从单个数字a开始出现然后分隔出来的#xff0c;如果mid落入左半部分那么当mid为偶数时nums[mid1]…1. 有序数组中的单一元素540
题目描述 算法原理 二分查找解题关键就在于去找到数组的二段性这里数组的二段性是从单个数字a开始出现然后分隔出来的如果mid落入左半部分那么当mid为偶数时nums[mid1]等于nums[mid]当mid为奇数时nums[mid]等于nums[mid-1]mid落入右半部分则相反。 细节 循环内的判断条件首先需要判断mid是偶数还是奇数接着还要判断相等的关系是比较麻烦的。我们发现规律当mid为偶数异或1时就会得到mid1当mid为奇数异或1时就会得到mid-1因此我们的判断条件直接简化为nums[mid]是否等于nums[mid^1]。 代码如下
class Solution {public int singleNonDuplicate(int[] nums) {int left 0, right nums.length - 1;while (right left) {int mid left (right - left) / 2;if (nums[mid] nums[mid ^ 1]) {left mid 1;} else {right mid;}}return nums[right];}
}题目链接
2. 寻找旋转排序数组中的最小值 II154
题目描述
算法原理 nums数组的二段性体现在nums[right]前半部分旋转过去的值是大于等于nums[right]的后半部分的值都是小于等于nums[right]。不过这题需要注意的地方就是因为数值是可以重复的所以当nums[mid]等于nums[right]的时候我们是不知道mid是落在前半部分还是后半部分的为了解决这种情况我们直接将right向左移动一位即可移动之后因为我们求的是最小值所以不会影响结果并且达到了一种去重的效果。 代码如下
class Solution {public int findMin(int[] nums) {int left 0, right nums.length - 1;while (left right) {int mid left (right - left) / 2;if (nums[mid] nums[right]) {left mid 1;} else if (nums[mid] nums[right]) {right mid;} else {right - 1;}}return nums[right];}
}题目链接
3. 搜索二维矩阵74
题目描述
算法原理 这一题可以使用朴素二分查找的思想来解决将多维数组看作一维的数组此时铺开来left0、rightm*n-1得到的mid位置的值在二维数组中可以表示为matrix[mid/n]matrix[mid%n]这里的m就是数组的维度数n就是每个维度的元素个数。 代码如下
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m matrix.length;int n matrix[0].length;int left 0, right m * n - 1;while (left right) {int mid left (right - left) / 2;if (matrix[mid / n][mid % n] target) {right mid - 1;} else if (matrix[mid / n][mid % n] target) {left mid 1;} else {return true;}}return false;}
}题目链接
