BM18 二维数组中的查找
描述
在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]
给定 target = 7，返回 true。
给定 target = 3，返回 false。
输入：
7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]返回值：
true说明：
存在7，返回true输入：
1,[[2]]返回值：
false题目的主要信息：
- 矩阵的行元素和列元素都是有序的，从左到右递增，从上到下递增，完全递增元素不会有重复
- 找到矩阵中有没有给定元素即可
方法1：二分查找（推荐使用）
知识点：分治
分治即“分而治之”，“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题，子问题继续按照这样划分，直到问题可以被轻易解决；“治”指的是将子问题单独进行处理。经过分治后的子问题，需要将解进行合并才能得到原问题的解，因此整个分治过程经常用递归来实现。
具体做法：
- step 1：首先获取矩阵的两个边长，判断特殊情况。
- step 2：首先以左下角为起点，若是它小于目标元素，则往右移动去找大的，若是他大于目标元素，则往上移动去找小的。
- step 3：若是移动到了矩阵边界也没找到，说明矩阵中不存在目标值。
public class Solution {
public boolean Find(int target, int [][] array) {
//优先判断特殊
if(array.length == 0)
return false;
int n = array.length;
if(array[0].length == 0)
return false;
int m = array[0].length;
//从最左下角的元素开始往左或往上
for(int i = n - 1, j = 0; i >= 0 && j < m; ){
//元素较大，往上走
if(array[i][j] > target)
i--;
//元素较小，往右走
else if(array[i][j] < target)
j++;
else
return true;
}
return false;
}
}方法2：暴力法
1. 分析
挨个遍历数组，如果找到就返回 true
public class Solution {
public boolean Find(int target, int [][] array) {
for(int i=0;i<array.length;i++){
for(int j=0;j<array[0].length;j++){
if(array[i][j] == target){
return true;
}
}
}
return false;
}
}BM19 寻找峰值
给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
如输入[2,4,1,2,7,8,4]时，会形成两个山峰，一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰，如下图所示：
示例1
输入：
[2,4,1,2,7,8,4]返回值：
1说明：
4和8都是峰值元素，返回4的索引1或者8的索引5都可以示例2
输入：
[1,2,3,1]返回值：
2说明：
3 是峰值元素，返回其索引 2</>代码
下面进行分析：
1、首先理解题目：峰值，即当前值左右两边的值都比它小，边界只要一边比它小即可
2、分析：
（1）如果只有一个数值，直接返回0；
（2）如果有两个数值，谁大就返回谁的下标；
（3）考虑边界：
a. 左边界，即下标为0的数值，只要它比右边的数值大，那它就是峰值；题目要求只要找出一个峰值就行了，因此这个条件可以优先判断，满足返回即可；
b. 右边界，即最后一个数值，只要它比左边的数值大，那它就是峰值；剩下所有数值都遍历过之后无峰值才判断该边界条件；
public class Solution {
public int findPeakElement (int[] nums) {
return findPeek(nums, 0, nums.length - 1);
}
public int findPeek(int[] nums, int left, int right) {
if (left == right) { // 区间只有一个元素时进行判断
if (nums.length == 1) { // 数组本来就一个元素，则一定是峰值
return left;
} else { // 数组大于一个元素
if (left > 0 && left < nums.length - 1) { // 该元素位于中间
if (nums[left] > nums[left - 1] && nums[left] > nums[left + 1]) {
return left;
}
} else if (left == 0) { // 该元素位于左侧
if (nums[left] > nums[left + 1]) {
return left;
}
} else if (right == nums.length - 1) { // 该元素位于右侧
if (nums[right] > nums[right - 1]) {
return right;
}
}
}
} else { // 区间大于一个元素时分治
int mid = (left + right) >> 1;
int lres = findPeek(nums, left, mid); // 找左侧的峰值
int rres = findPeek(nums, mid + 1, right); // 找右侧的峰值
if (lres != -1) return lres;
if (rres != -1) return rres;
}
return -1; // 找不到峰值返回-1
}
}import java.util.*;
public class Solution {
public int findPeakElement (int[] nums) {
// write code here
// 两种特殊情况,第一种length为1,
if (nums.length == 1) return 0;
//第二种峰值在尾部
if (nums[nums.length - 1] > nums[nums.length - 2]) return nums.length - 1;
//峰值在中间
for (int i = 1; i < nums.length - 1; i++) {
if (nums[i - 1] < nums[i] && nums[i + 1] < nums[i]) {
return i;
}
}
//峰值在头部
return 0;
}
}// *****暴力求解完事******
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return int整型
*/
public int findPeakElement (int[] nums) {
// write code here
if(nums.length == 2)
if(nums[0] > nums[1])
return 0;
else return 1;
for(int i = 1; i < nums.length-1; i++){
if(nums[i] > nums[i+1] && nums[i] > nums[i-1])
return i;
if(nums[i]< nums[i+1] && i == nums.length-2)
return i+1;
}
return 0;
}
}