🤞目录🤞
【大家好，我是爱干饭的猿，如果喜欢这篇文章，点个赞👍，关注一下吧，后续会一直分享题目与算法思路】
🏀1. 二维数组中的查找
描述：
在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[ [1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15] ]
给定 target = 7，返回 true。
给定 target = 3，返回 false。
数据范围：矩阵的长宽满足 0 \le n,m \le 5000≤n,m≤500 ， 矩阵中的值满足 0 \le val \le 10^90≤val≤109
进阶：空间复杂度 O(1)O(1) ，时间复杂度 O(n+m)O(n+m)
解题思路：
🎈1. 方法一： 查找的本质是排除，使用可以用双重循环，如果arr[i][j] = target，则找到target，返回true，但是效率太低。
🎈2. 方法二：我们可以将target 与右上角值比较，达到每次排除一行或一列的效果
如果target 大于右上角值，则排除当前行；
如果target 小于右上角值，则排除当前列；
🎈方法二：代码如下：
public class SearchIN2DArr_1 { public boolean Find(int target, int [][] array) { if(array.length == 0 ){ return false; } int row = 0; int col = array[0].length - 1; while(row < array.length && col >= 0){ // array[row][col] 一定是当前行最大的 if(target < array[row][col]){ // 排除当前列 col --; }else if(target > array[row][col]){ // 排除当前行 row ++; }else { return true; } } return false; } }
🏀2. 旋转数组的最小数字
描述：
有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。
编辑
数据范围：1 \le n \le 100001≤n≤10000，数组中任意元素的值: 0 \le val \le 100000≤val≤10000
要求：空间复杂度：O(1)O(1) ，时间复杂度：O(logn)O(logn)
解题思路：
🎈1. 方法一：理论上，我们可以进行一次遍历即可，因为是非降序数组arr[i] < arr[i+1]，所以当旋转后，遇到arr[i] > arr[i+1]时，该值（arr[i+1]）就是最小值。
🎈2. 方法二：我们可以使用二分法进行定位，时间复杂度更低，定义 left 最左，right 最右，mid 中间
因为数组非降序，所以
如果arr[left] <= arr[mid]，旋转数组就在mid右侧[mid...right]，使left = mid；
如果arr[left] > arr[mid]，旋转数组就在mid右侧[left...mid]，使right = mid；
范围不断缩小，当left 与 right 相邻时，arr[right] 就是最小值。
🎈方法一：代码如下
public int minNumberInRotateArray1(int [] array) { if(array == null || array.length == 0){ return 0; } for(int i = 0; i < array.length-1; i++){ // 遇到arr[i] > arr[i+1]时，该值arr[i+1]就是最小值 if(array[i] > array[i+1]){ return array[i+1]; } } return array[0]; }
🎈方法二：代码如下
public static int minNumberInRotateArray2(int [] array) { // 判空 if (array == null || array.length == 0) { return 0; } int left = 0; int right = array.length - 1; int mid = 0; while(array[left] >= array[right]){ if (right - left == 1) { mid = right; break; } mid = left + ((right - left) >> 1); // 恰巧left right mid 值相等 if (array[left] == array[mid] && array[left] == array[right]) { int restlt = array[left]; for (int i = left + 1; i < right; i++) { if (restlt > array[i]) { restlt = array[i]; } } return restlt; } if (array[left] <= array[mid]) { // 旋转数在右侧，[mid...right] left = mid; } else { // 旋转数在左侧，[left...mid] right = mid; } } return array[mid]; }
🏀3. 调整数组顺序使奇数位于偶数前面
描述：
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。(进阶：保证奇偶位置不变)
示例：
[1, 2, 3, 4, 5]
输出：
[1, 3, 5, 2, 4]
解题思路：
🎈1. 方法一：使用二分法，定义 left 最左，right 最右，遍历数组，找 arr[left] 为偶数，arr[right] 为奇数，然后交换两值。
🎈2. 方法二：（进阶：保证奇偶位置不变）：因为相对位置不能改变，不能用二分法，用直接插入法。遍历数组，当找到奇数时，将该奇数之前的偶数都后移一位，然后该奇数存入偶数前的位置。
🎈方法一：代码如下
// 若相对位置可以改变，使用二分法 public static void reOrderArray1(int [] array) { int left = 0; int right = array.length - 1; while (left < right){ // &运算 0&1=0，1&1=1，1&0=0，0&0=0 while ((array[left] & 1) == 1 && left < right){ // 找到偶数 left++; } while ((array[right] & 1) == 0 && left < right){ // 找到奇数 right--; } if(left < right){ // 交换三联 int temp = array[left]; array[left] = array[right]; array[right] = temp; } } }
🎈方法二：代码如下
// 因为相对位置不能改变，不能用二分法，用直接插入 public static void reOrderArray2(int [] array) { // 记录已排奇数的末位置索引 int k = 0; for (int i = 0; i < array.length; i++) { // &运算 0&1=0，1&1=1，1&0=0，0&0=0 // 找到奇数 if((array[i] & 1) == 1){ int temp = array[i]; int j = i; // 将 k~j 的偶数后移 while(k < j){ array[j] = array[j-1]; j--; } array[k] = temp; k++; } } }
