大家好！我是未来村村长，就是那个“请你跟我这样做，我就跟你这样做！”的村长👨?🌾！
||Algorithm Day||
? 未来村村长正推出一系列【Algorithm Day】文章，该系列文章重在提高本人的算法能力，希望能在刷题过程中总结一般方法，提高个人的逻辑思维能力和解题能力。该系列文章以天数为轴，从一个个算法中逐步强化算法相关知识点。
? ”算法之路，任重而道远。“🌱|day 4|🌾
文章目录
[声明：以下题目的内容或部分解法来自牛客网或Leetcode，为个人学习总结和记录，也方便大家学习和查阅]
一、寻找第K大
1、题目描述
（1）描述
? 有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
? 给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。
? 要求：时间复杂度 O(nlogn)，空间复杂度 O(1)
（2）示例
2、思路分析
（1）实现一思路：优先队列
? 这里虽然要求使用快速排序的算法，但是这里补充一个使用PriorityQueue的方法，主要是方便后续的使用。
? 【ps：掌握快速排序、二分查找、反转链表、堆的数据结构很基础很重要】
? PriorityQueue是小顶堆，我们只需要将元素全部通过add添加到小顶堆中，然后到n-k位置的数进行返回即可。
（2）实现二思路：快速二分法
? 对快速排序的方法进行优化，在排序过程中确定k。在每轮双指针遍历时结束时，比较K与指针对应的位置，如果相等，则已经找到K了返回结果，小于则对右边进行双指针遍历，大于则对左边进行双指针遍历。
3、Java实现
（1）实现一：优先队列
public class Solution {
public int findKth(int[] a, int n, int K) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
for(int i:a) heap.add(i);
for(int i = 0;i<(n-K);i++) heap.poll();
return heap.poll();
}
}
（2）实现二：快速二分法
public class Solution {
static int res;
public static int findKth(int[] a, int n, int K) {
//n-k是对应第K大在排序后数组中的位置
int k = n-K;
quickSort(a, 0, a.length - 1, k);
return res;
}
public static void quickSort(int[] arr, int left, int right, int k) {
//快速排序常规操作
int i = left;
int j = right;
//常规return
if (i > j) return;
int base = arr[left];
while (j > i) {
//一定要先从右往左遍历
while (arr[j] >= base && j > i) j--;
while (arr[i] <= base && j > i) i++;
if (j > i) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[left] = arr[i];
arr[i] = base;
if (i == k){
res = base;
return;
}
//分情况进行排序，这样每次只用排一半的数组
if (i < k) quickSort(arr, i+1, right, k);
if (i > k) quickSort(arr, left, i-1, k);
}
}
快速排序排坑：
-
特别是涉及到交换两个元素的值时，主要不要替换错
int t = arr[i]; arr[i] = arr[j]; arr[j] = t;//arr[j] = arr[i];是错的！ -
指针遍历部分
//一 while (arr[j] >= base && j > i) j--; while (arr[i] <= base && j > i) i++; //二 while (arr[i] <= base && j > i) i++; while (arr[j] >= base && j > i) j--;? 一和二换了个顺序，会导致数组排序不成功。一定是先从右开始遍历，再从左开始遍历。为什么，我们举个例子：
{4,6,5,7,9,3}? 上述数组，我们如果先从右遍历，首先基准位为4，然后我们向右找到6这个数，等待交换。向左找到3这个数，开始交换。6和3进行交换得到{4,3,5,7,9,6}，继续向右找到5等待交换，向左也找到5，遍历停止。5和4进行交换得到{5,3,4,7,9,6}。
? 我们发现5比4大却在5的前面，这时因为先从左开始向右遍历的话，最后一次左指针停止时遇到的数比基准数大，这样等到右指针遇到左指针时，就会发生交换位比基准位的数大的情况。
-
忘记return
if (left > right) return;? 这个不是错误判断，使用二分法时，因为每次都取(mid+1,right)或(left,mid-1)作为下一个执行区域，分解到最终一定会分到只剩一个元素或没有元素，这时就需要一个return进行返回
4、相关知识补充
? PriorityQueue是Java集合中的优先队列，是一个小顶堆数据结构，其常用方法如下：
| 常用方法 | 说明 |
|---|---|
| add(E e) | 在队尾添加元素，并调整堆结构 |
| peek() | 获取队首元素，失败返回null |
| poll() | 获取并删除队首元素，失败返回null |
| remove() | 获取并删除队首元素，失败时抛出异常 |
| element() | 获取队首元素，失败时抛出异常 |
二、矩阵元素查找
1、题目描述
（1）描述
? 已知一个有序矩阵mat，同时给定矩阵的大小n和m以及需要查找的元素x，且矩阵的行和列都是从小到大有序的。设计查找算法返回所查找元素的二元数组，代表该元素的行号和列号(均从零开始)。保证元素互异。
? 要求：空间复杂度 O(1)，时间复杂度 O(n+m)
（2）示例
2、思路分析
? 如下图所示，我们定义两个指针row和col，col扫描列，row扫描行。假设我们在二维矩阵mat{{1,3,5,7},{2,4,6,8}}寻找x元素6。当然可以通过两个for循环找到，但是这样的复杂度将会是O(n2)。
? 定义row从0开始，定义col从m-1开始，如果mat[row][col]大于6，因为其行列都是递增的，我们则会将col往左移动一位。如果mat[row][col]小于6，我们将row向下移动一位。
? 为什么先执行col再执行row呢？因为我们从顶层的最后一个元素开始扫描，这样row不能退，则当遇到大于x的数时，只需要移动col，当遇到小于x的数时，col也不能向右移动。这样就确保扫描的正确性了。
3、Java实现
public class Solution {
public int[] findElement(int[][] mat, int n, int m, int x) {
//定义扫描指针
int row = 0,col = m-1;
//开始扫描
while(row<=n && col>=0){
if(mat[row][col]>x) col--;
if(mat[row][col]<x) row++;
if(mat[row][col]==x) return new int[]{row,col};
}
return new int[]{};
}
}
附：第一次没看清问题的答案，如果在原题目基础上加上以下条件：且第n行的元素都比第n-1行的数据要大(n>1)，则可以直接使用二分法进行解答。
public class Solution {
public int[] findElement(int[][] mat, int n, int m, int x) {
//1、确定所在行
int res[] = new int[2];
int i = 0;
while(i<(n-1) && x>mat[i][0]){
i++;
}
if(i==(n-1)) res[0] = i;
if(i<(n-1)) res[0] = (i-1);
int l = 0;
int r = m-1;
while(r>=l){
int mid = (l+r)/2;
if(mat[res[0]][mid]>x) r = mid - 1;
if(mat[res[0]][mid]<x) l = mid + 1;
if(mat[res[0]][mid] == x) {
res[1] = mid;
break;
}
}
return res;
}
}
4、相关知识补充
? 可以发现查找满足特定要求的元素，经常会使用到二分或双指针。
三、在两个长度相等的排序数组中找到上中位数
1、题目描述
（1）描述
? 给定两个递增数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。
? 要求：时间复杂度 O(n)，空间复杂度 O(1)
? 进阶：时间复杂度为O(logN)，空间复杂度为O(1)
（2）示例
2、思路分析
? 两个有序数组找上中位数，可以看作把两个数组合并成一个排序数组，取到mid = length/2上的数。
? 这样的题目我们已经很有经验了，可以想到以下解法：
- 使用PriorityQueue，将两数组的元素按顺序加到该小顶堆中，然后逐个删除取到mid = length/2的数。
- 使用双指针，定义一个新数组arr，通过扫描的方式，将两个数组元素按顺序加入新数组，然后直接返回arr[mid]【我们实现第二种】
- 使用双指针，通过扫描的方式扫描两个元素，无需添加到新数组，当扫描次数达到mid时即是我们所需要的元素，将该元素返回即可
3、Java实现
public class Solution {
public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
//定义两个指针用于扫描两个数组
int i=0,j=0;
int l = arr1.length - 1;
//建立list用于存储元素数据
ArrayList<Integer> list = new ArrayList<>();
//当只有长度为1时，直接返回较小值
if(l==0) return arr1[i]>arr2[j]?arr2[j]:arr1[i];
//开始扫描，较小值先add入list
while(i<=l && j<=l){
if(arr1[i]<=arr2[j]){
list.add(arr1[i]);
//当有一个数组扫描提前完成，则说明该数组最后一个元素为上中位数
if(i==l) return list.get(l);
i++;
}
if(arr1[i]>=arr2[j]){
list.add(arr2[j]);
if(j==l) return list.get(l);
j++;
}
}
//上述代码不一定将所有元素都装到list中，但是一定能装到上中位数
return list.get(l);
}
}
四、总结
? 今天的内容主要是对于三个查找题进行了梳理，我们发现当需要我们查找某一个满足要求的元素时，多数可以用二分法和双指针法解决。
（1）二分法
? 二分法需要用到两个指针，一个left，一个right，每次会取一个mid=(left+right)/2，然后通过条件比较，如果在右半部分，将right=mid-1；如果在左半部分，将left=mid+1，最后搜索到的mid就是我们要查找的值。
? 使用二分法要注意左右指针越界的问题，left+1是否大于rigth，如果是递归的话，在大于时要进行return操作。
（2）双指针法
? 双指针遍历的话，注意指针什么时候停止，怎么让其停下来，不然很容易进入死循环。
——————————————————
作者：未来村村长
参考：牛客网面向编程题
图源：部分源于牛客网
个人网站：www.76pl.com
👨?🌾点个关注，在未来村不会迷路👩?🌾
——————————————————
