第 1 天_二分查找
- 前言
- 34. 在排序数组中查找元素的第一个和最后一个位置
- 题解
- 官方
- 33. 搜索旋转排序数组
- 题解
- 官方
- 74. 搜索二维矩阵
前言
这是陈旧已久的草稿2021-11-09 19:33:44
当时在学习数据结构,然后再LeetCode上找了一个算法基础。
但是后来又没做了。
现在2024-5-12 22:03:18,发布到[LeetCode]专栏中。
34. 在排序数组中查找元素的第一个和最后一个位置
难度 中等
给定一个按照升序排列的整数数组 nums
,和一个目标值 target
。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target
,返回 [-1, -1]
。
进阶:
- 你可以设计并实现时间复杂度为
O(log n)
的算法解决此问题吗?
示例 1:
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
示例 2:
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
示例 3:
输入:nums = [], target = 0
输出:[-1,-1]
提示:
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
- nums 是一个非递减数组
- -109 <= target <= 109
题解
思路:左右指针
因为数组nums是升序给出的
class Solution {public int[] searchRange(int[] nums, int target) {int [] searchRange=new int[2];int left=0;int right=nums.length-1;boolean findL=false;boolean findR=false;while((!findL||!findR)&&(left<=right)){if(!findL){if(nums[left]==target){findL=true;searchRange[0]=left;}else{left++;}}if(!findR){if(nums[right]==target){findR=true;searchRange[1]=right;}else{right--;}}}if (!findL&&!findR){searchRange[0]=-1;searchRange[1]=-1;}return searchRange;}
}
官方
思路:二分查找
class Solution {public int[] searchRange(int[] nums, int target) {int leftIdx = binarySearch(nums, target, true);int rightIdx = binarySearch(nums, target, false) - 1;if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {return new int[]{leftIdx, rightIdx};} return new int[]{-1, -1};}public int binarySearch(int[] nums, int target, boolean lower) {int left = 0, right = nums.length - 1, ans = nums.length;while (left <= right) {int mid = (left + right) / 2;if (nums[mid] > target || (lower && nums[mid] >= target)) {right = mid - 1;ans = mid;} else {left = mid + 1;}}return ans;}
}作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-3-4/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
33. 搜索旋转排序数组
难度 中等
整数数组 nums
按升序排列,数组中的值 互不相同 。
在传递给函数之前,nums
在预先未知的某个下标 k
(0 <= k < nums.length
)上进行了 旋转,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
(下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7]
在下标 3
处经旋转后可能变为 [4,5,6,7,0,1,2]
。
给你 旋转后 的数组 nums
和一个整数 target
,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1
。
示例 1:
输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4
示例 2:
输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1
示例 3:
输入:nums = [1], target = 0
输出:-1
提示:
- 1 <= nums.length <= 5000
- -104<= nums[i] <= 104
nums
中的每个值都 独一无二- 题目数据保证
nums
在预先未知的某个下标上进行了旋转 - -104 <= target <= 104
进阶:你可以设计一个时间复杂度为 O(log n)
的解决方案吗?
题解
思路:左右指针
class Solution {public int search(int[] nums, int target) {int left=0;int rigth=nums.length-1;while(left<=rigth){if(nums[left]==target){return left;}if(nums[rigth]==target){return rigth;}left++;rigth--;}return -1;}
}
官方
思路:二分查找
class Solution {public int search(int[] nums, int target) {//最简单问题int n = nums.length;if (n == 0) {return -1;}if (n == 1) {return nums[0] == target ? 0 : -1;}//普通int l = 0, r = n - 1;//二分法while (l <= r) {int mid = (l + r) / 2;if (nums[mid] == target) {return mid;}if (nums[0] <= nums[mid]) {//在前一半if (nums[0] <= target && target < nums[mid]) {r = mid - 1;} else {l = mid + 1;}} else {if (nums[mid] < target && target <= nums[n - 1]) {l = mid + 1;} else {r = mid - 1;}}}return -1;}
}作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/sou-suo-xuan-zhuan-pai-xu-shu-zu-by-leetcode-solut/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
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
提示:
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 100
- -104 <= matrix[i][j], target <= 104
思路
因为每行的第一个整数大于前一行的最后一个整数。
所以先要从第一列找
找出target在哪一列