「剑指Offer」Day05：查找算法（中等）
剑指 Offer 04. 二维数组中的查找
题目描述
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
现有矩阵 matrix 如下： [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] 给定 target = 5，返回 true。 给定 target = 20，返回 false。题目链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
思路
二分查找，目标值在当前行数组的范围内就进行二分查找
实现代码
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
int n = matrix.length;
if(n == 0) {
return false;
}
for(int i = 0; i < n; i++){
int m = matrix[i].length;
if(m > 0 && target >= matrix[i][0] && target <= matrix[i][m - 1]){
//目标值在当前行数组的范围内就进行二分查找
if(binarySearch(matrix[i], target)){
return true;
}
}
}
return false;
}
public boolean binarySearch(int[] arr, int target){ //二分查找
int left = 0;
int right = arr.length - 1;
int mid = 0;
while(left <= right){
mid = left + (right - left) / 2;
if(arr[mid] == target){
return true;
}else if(arr[mid] < target){
left = mid + 1;
}else{
right = mid - 1;
}
}
return false;
}
}
剑指 Offer 11. 旋转数组的最小数字
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。输入：[3,4,5,1,2]题目链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
输出：1
方法一：暴力解法
直接遍历，因为数组没旋转之前为递增的，所以找到第一个当前元素小于前一个元素的位置，即为旋转数组的最小值
class Solution {
public int findMin(int[] nums) {
for(int i = 1; i < nums.length; i++){
if(nums[i] < nums[i-1]){
return nums[i];
}
}
//没有旋转第一个元素就为最小值
return nums[0];
}
}
方法二：二分法
思路
数组中最特殊的位置是左边位置left和右边位置right，将它们与中间位置mid的值进行比较，进而判断最小数字出现在哪里。
- 左边有序数组是大于等于右边有序数组的
-
当
时，可知最小值在左边有序数组，但 mid 有可能是最小值，下一轮搜索区间是 [left, mid]
-
当
时，可知最小值在右边有序数组，下一轮搜索区间是 [mid + 1, right]
-
当
时，无法确定最小值在哪边，但可知无论nums[right]是否为最小值都有替代者，因此可通过缩小边界忽略该右端点
用左边位置left和中间位置mid的值进行比较是否可以？
举例：[3, 4, 5, 1, 2] 与 [1, 2, 3, 4, 5] ，此时，中间位置的值都比左边大，但最小值一个在后面，一个在前面，因此这种做法不能有效地减治。
class Solution {
public int minArray(int[] numbers) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (numbers[mid] < numbers[right]) { //最小值在左边，mid位置也有可能是最小值
right = mid;
} else if (numbers[mid] > numbers[right]) { //最小值在右边
left = mid + 1;
} else { //相等就缩小右边界
right -= 1;
}
}
return numbers[left];
}
}
剑指 Offer 50. 第一个只出现一次的字符
题目描述
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
输入：s = "abaccdeff"
输出：'b'
方法一：有序哈希
目的是找出第一个只出现一次的字符，使用LinkedHashMap保证插入的顺序
class Solution {
public char firstUniqChar(String s) {
Map<Character, Integer> map = new LinkedHashMap<>();
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
int val = map.getOrDefault(c, 0);
map.put(c, val + 1);
}
for(char key : map.keySet()){
if(map.get(key) == 1){
return key;
}
}
return ' ';
}
}
