剑指offer day5 查找算法(中等)
day5题目:剑指 Offer 04. 二维数组中的查找、剑指 Offer 11. 旋转数组的最小数字、剑指 Offer 50. 第一个只出现一次的字符
知识点:数组、二分、哈希,难度为中等、简单、简单
学习计划链接:「剑指 Offer」 - 学习计划
数组、二分
中等
数组、二分
简单
字符串、哈希
简单
在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下:
给定 target = 5
,返回 true
。
给定 target = 20
,返回 false
。
限制:
0 <= n <= 1000
0 <= m <= 1000
注意: 本题与主站 240 题相同:https://leetcode-cn.com/problems/search-a-2d-matrix-ii/
思路及代码
思路1:二分法+一些优化
思路2:站在数组右上角看这其实是一个二叉搜索树:二维数组中的查找 - 力扣
二叉搜索树中左边元素都比他小,右边元素都比他大,故这里若当前元素小于目标值则向右(实际是向下r++)找,大于目标值则向左(实际是向左c--)找。
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers
,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如,数组 [3,4,5,1,2]
为 [1,2,3,4,5]
的一次旋转,该数组的最小值为 1。
注意,数组 [a[0], a[1], a[2], ..., a[n-1]]
旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]
。
示例 1:
示例 2:
提示:
n == numbers.length
1 <= n <= 5000
-5000 <= numbers[i] <= 5000
numbers
原来是一个升序排序的数组,并进行了1
至n
次旋转
注意:本题与主站 154 题相同:https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/
思路及代码
在之前做过的 33. 搜索旋转排序数组
有讲过:冲刺春招-精选笔面试 66 题大通关 day6
因为可能有重复的元素,故此题还需注意重复元素处的 --r
这题的题解可以看官方的很详细:旋转数组的最小数字
在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母。
示例 1:
示例 2:
限制:
0 <= s 的长度 <= 50000
思路及代码
遍历一遍用哈希表存,出现过两次以上的都按两次算。
最后更新于
这有帮助吗?