给定一个有序数组arr，从左到右依次表示X轴上从左往右点的位置，给定一个正整数K，返回如果有一根长度为K的绳子，最多能盖住几个点，绳子的边缘点碰到X轴上的点，也算盖住。
- 滑动窗口，规定L,R判断此时R -> L是否大于给定的长度K ，一直增大R，直到找到此时以L开头时的最大长度记录此时的值。然后向右移动L继续上面的步骤。
/**
给定一个有序数组arr，从左到右依次表示X轴上从左往右点的位置，给定一个正整数K，
返回如果有一根长度为K的绳子，最多能盖住几个点，绳子的边缘点碰到X轴上的点，也算盖住。
*/
public class CoverNum {
public static int coverNum(int[] arr,int k){
if(arr == null || arr.length == 0 || k < 0){
return 0;
}
int n = arr.length;
int L = 0;
int R = 0;
int max = 0;
// 枚举所有开头
while (L < n){
while (R < n && (arr[R] - arr[L] <= k)){
R++;
}
max = Math.max(max,R - L);
L++;
}
return max;
}
}
括号有效配对是指：1）任何一个左括号都能找到和其正确配对的右括号，2）任何一个右括号都能找到和其正确配对的左括号有效的： (()) ()() (()()) 等无效的： (() )( 等。
问题一：怎么判断一个括号字符串有效？
问题二：如果一个括号字符串无效，返回至少填几个字符能让其整体有效
/**
* 括号有效配对是指：
* 1）任何一个左括号都能找到和其正确配对的右括号
* 2）任何一个右括号都能找到和其正确配对的左括号
* 有效的： (()) ()() (()()) 等
* 无效的： (() )( 等
* 问题一：怎么判断一个括号字符串有效？
* 问题二：如果一个括号字符串无效，返回至少填几个字符能让其整体有效
*/
public class Parentheses {
public static boolean isValid(String str){
if(str == null || str.length() == 0){
// 规定空串无效
return false;
}
char[] c = str.toCharArray();
int n = c.length;
int count = 0;
for (int i = 0; i < n; i++) {
// 遇到左括号count++
if(c[i] == '('){
count ++;
}else {
count --;
}
// 遇到右括号count--
if(count < 0){
return false;
}
}
return count == 0;
}
public static int needParentheses(String str){
char[] c = str.toCharArray();
int n = c.length;
int count = 0;
int need = 0;
for (int i = 0; i < n; i++) {
if(c[i] == '('){
count ++;
}else {
count --;
}
if(count == -1){
// 需要一个左括号来配对
need++;
count = 0;
}
}
// 最后count>=0;
// 如果count为正数，则是需要几个右括号来配对，加上需要几个左括号need
return need + count;
}
public static int needParentheses2(String str){
char[] c = str.toCharArray();
int n = c.length;
int count = 0;
int need = 0;
for (int i = 0; i < n; i++) {
if(c[i] == '('){
count ++;
}else {
if(count == 0){
need++;
}else {
count --;
}
}
}
// 最后count>=0;
// 如果count为正数，则是需要几个右括号来配对，加上需要几个左括号need
return need + count;
}
}
括号有效配对是指：1）任何一个左括号都能找到和其正确配对的右括号,2）任何一个右括号都能找到和其正确配对的左括号,返回一个括号字符串中，最长的括号有效子串的长度。
- 动态规划，生成一个记录位置结尾的形成的最长子串的数组。假设我们现在求i位置的最长有效子串的长度，我们已经知道i-1位置的最长有效子串长度为l，如果此时i位置时左括号，那么此时以i位置结尾不可能形成有效子串，则有效子串长度为0，若是以右括号结尾的那么我们可以看此时从i位置向前推l的长度的前一个位置是否是一个左括号，若不是则以i位置结尾的最长子串长度为0，若是那么我们可以确定以i位置结尾的最长子串的最小长度是l+2，还能不能更长我们要看此时最少形成的子串的开头位置的前一个位置为结尾的子串的长度相加。
/**
* 有效的最长子串
*/
public class MaxParenthesesLen {
public static int maxParenthesesLen(String str){
if(str == null || str.length() == 0){
return 0;
}
char[] c = str.toCharArray();
int n = c.length;
int[] dp = new int[n];
dp[0] = 0;
int max = 0;
for (int i = 1; i < n; i++) {
if(c[i] == ')'){
/**
* 下面两个if可以用这个替换
* int index = i - dp[i-1]-1;
* if(index >=0 && dp[index] =='('){
* dp[i] = dp[i-1]+2 +(index >0 ? dp[index-1] :0);
* }
*/
if(i-dp[i-1]-1 >= 0){
dp[i] = c[i-dp[i-1]-1] == '('? dp[i-1]+2:0;
}
if(i-dp[i-1]-2 >= 0){
dp[i] = dp[i] + dp[i-dp[i-1]-2];
}
}
max = Math.max(max,dp[i]);
}
return max;
}
// 求括号嵌套的深度,前提是括号字符串一定有效
// 一个变量count左括号加，右括号减，抓取遍历过程中的最大值
public static int deep(String str){
char[] c = str.toCharArray();
int max = 0;
int count = 0;
for (int i = 0; i < c.length; i++) {
count = c[i] == '('?count+1 : count-1;
max = Math.max(max,count);
}
return max;
}
public static void main(String[] args) {
String str = "((()))((()))()";
System.out.println(maxParenthesesLen(str));
System.out.println(deep(str));
}
}
有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色,这个正方形的颜色将 会被覆盖。目标是在完成染色之后,每个红色R都比每个绿色G距离最左侧近。 返回最少需要涂染几个正方形。如样例所示: s = RGRGR 我们涂染之后变成RRRGG满足要求了,涂染的个数为2,没有比这个更好的涂染方案。
- 题意就是要求红色在左边绿色在右边。我们可以在内个位置作一个分界线，计算满足要求的最少的便函个数，分割后会分成两个部分，左边部分需要把绿色变成红色，右边部分需要把红色变成绿色，没分一次统计此时的变换次数然后选出次数最少的。如果不优化每一次都会重新计算左边G的个数，右边R的个数，我们可以用预处理技巧收集每个位置左边个数，右边R的个数。
/**
* 有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。现在可以选择任意一个正方形然后用这两种颜
* 色的任意一种进行染色,这个正方形的颜色将 会被覆盖。目标是在完成染色之后,每个红色R都比每个绿色G距离最左侧近。
* 返回最少需要涂染几个正方形。如样例所示: s = RGRGR 我们涂染之后变成RRRGG满足要求了
* ,涂染的个数为2,没有比这个更好的涂染方案。
*/
public class GRNum {
public static int grNum(String str){
if(str == null || str.length() ==0){
return 0;
}
char[] c = str.toCharArray();
int n = c.length;
// 由于是从左向右遍历我们可以用一个变量表示左边遍历过得G的数量，
int gNum = 0;
// 用另一个变量表示总共的R的数量
int rNum = 0;
for (int i = 0; i < n; i++) {
if(c[i] == 'R'){
rNum += 1;
}
}
int min = Integer.MAX_VALUE;
int res = 0;
// 遍历到 表示此时左边部分是 0~i-1,右边部分i~n-1
// 有两个边界条件，全是G和全是R
for (int i = 0; i < n; i++) {
// res = 左边部分的G的个数加上右边部分R的个数
res = gNum + rNum;
if(c[i] == 'G'){
gNum += 1;
}else{
rNum -= 1;
}
min = Math.min(res,min);
}
// 全是R的时候
min = Math.min(min,gNum+rNum);
return min;
}
public static void main(String[] args) {
String str = "GGRRRR";
System.out.println(grNum(str));
}
}
给定一个N*N的矩阵matrix，只有0和1两种值，返回边框全是1的最大正方形的边长长度。
例如:
01111
01001
01001
01111
01011
其中边框全是1的最大正方形的大小为4*4，所以返回4。
- 边长为N的矩阵中长方形的个数数量级是O(N^4)
- 正方形是O(N^3)
- 在矩阵中枚举所有点，枚举所有可能的边长让后校验此边长下是否符合题意都是1，可以完成，但是每次判断是否都是1时需要重新计算复杂度高,用预处理技巧加速校验过程。
public class OneMatrix {
public static int oneMatrix(int[][] matrix){
if(matrix == null || matrix.length == 0){
return 0;
}
int rowN = matrix.length;
int colN = matrix[0].length;
// row[i][j] 表示i，j这个点开始右边连续1的长度
int[][] row = new int[rowN][colN];
// col[i][j] 表示i,j位置开始所有向下最长的连续1的长度
int[][] col = new int[rowN][colN];
generateRowArr(matrix,row,rowN - 1,colN - 1);
generateColArr(matrix,col,rowN - 1,colN - 1);
// 枚举所有点和边长
int max = 0;
for (int i = 0; i < rowN; i++) {
for (int j = 0; j < colN; j++) {
for (int k = 1;k <= rowN;k++){
// 计算此时点是否符合
if(isV(row,col,i,j,k)){
max = Math.max(max,k);
}
}
}
}
return max;
}
private static boolean isV(int[][] r,int[][] c,int i ,int j,int k){
// 取出水平方向的长度
int rowL = r[i][j];
// 竖直方向的长度
int colL = c[i][j];
if(rowL >= k && colL >= k){
return true;
}
return false;
}
private static void generateRowArr(int[][] matrix,int[][] r,int row,int col){
for(int i = 0;i <= row ;i++){
r[i][col] = matrix[i][col] == 1 ? 1 : 0;
}
for (int i = 0; i <= row; i++) {
// 每一行从右向左填
for (int j = col - 1; j >= 0; j--) {
r[i][j] = matrix[i][j] == 1 ? 1 + r[i][j+1]:0;
}
}
}
private static void generateColArr(int[][] matrix,int[][] c,int row,int col){
for(int i = 0;i <= col ;i++){
c[row][i] = matrix[row][i] == 1 ? 1 : 0;
}
// 从下往上填
for (int i = row-1; i >= 0 ; i--) {
for (int j = 0; j <= col; j++) {
c[i][j] = matrix[i][j] == 1 ? 1 + c[i+1][j]:0;
}
}
}
public static void main(String[] args) {
int[][] arr = new int[][]{
{0,1,1,1,1},
{0,1,0,0,1},
{0,1,0,0,1},
{0,1,1,1,1},
{0,1,0,1,1}
};
System.out.println(oneMatrix(arr));
}
}
有n个打包机器从左到右一字排开，上方有一个自动装置会抓取一批放物品到每个打 包机上，放到每个机器上的这些物品数量有多有少，由于物品数量不相同，需要工人 将每个机器上的物品进行移动从而到达物品数量相等才能打包。每个物品重量太大、 每次只能搬一个物品进行移动，为了省力，只在相邻的机器上移动。请计算在搬动最 小轮数的前提下，使每个机器上的物品数量相等。如果不能使每个机器上的物品相同， 返回-1。 例如[1,0,5]表示有3个机器，每个机器上分别有1、0、5个物品，经过这些轮后:
第一轮:1 0 <- 5 => 1 1 4第二轮:1 <- 1 <- 4 => 2 1 3第三轮:2 1 <- 3 => 2 2 2
移动了3轮，每个机器上的物品相等，所以返回3
例如[2,2,3]表示有3个机器，每个机器上分别有2、2、3个物品， 这些物品不管怎么移动，都不能使三个机器上物品数量相等，返回-1枚举每个位置,比如现在一共有sum个货物，现在在i位置，i的左边实际有货物L ，右边实际有货物R，达标情况下每个位置的货物为x,i的左边有机器n,右边有机器m，则有如下情况。
1.如果左边实际的货物比nx大，右边实际货物比mx大，则取两边Max((L-nx),(R-mx));
2.如果L-（nx）>0,R-(mx)<0, 取绝对值大的。
3.如果L-（nx）<0,R-(mx)>0, 取绝对值大的。
4.如果L-（nx）<0,R-(mx)<0,绝对值相加。
遍历每个位置去最大值。
/**
* 有n个打包机器从左到右一字排开，上方有一个自动装置会抓取一批放物品到每个打 包机上，放到每个机器上的这些物品数量有多有少，
* 由于物品数量不相同，需要工人 将每个机器上的物品进行移动从而到达物品数量相等才能打包。每个物品重量太大、
* 每次只能搬一个物品进行移动，为了省力，只在相邻的机器上移动。请计算在搬动最 小轮数的前提下，使每个机器上的物品数量相等
* 。如果不能使每个机器上的物品相同， 返回-1。 例如[1,0,5]表示有3个机器，每个机器上分别有1、0、5个物品，经过这些轮后:
* 第一轮:1 0 <- 5 => 1 1 4第二轮:1 <- 1 <- 4 => 2 1 3第三轮:2 1 <- 3 => 2 2 2
* 移动了3轮，每个机器上的物品相等，所以返回3
* 例如[2,2,3]表示有3个机器，每个机器上分别有2、2、3个物品， 这些物品不管怎么移动，都不能使三个机器上物品数量相等，返回-1
*/
public class Machine {
public static int machine(int[] arr){
if(arr == null || arr.length == 0){
return -1;
}
// 求总数一个有几件物品
int n = arr.length;
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}
// 不能被整除也不符合要求
if(sum % n != 0){
return -1;
}
// 左边实际总数(右边货物的数量只需要总数减去左边的和i位置的数量就可)
int left = 0;
// 平均每个位置应该有的货物数量
int average = sum / n;
int max = 0;
int temp = 0;
for (int i = 0; i < n; i++) {
if(((left - i * average) < 0) && ((sum - left-arr[i]) - ((n-i-1)*average))<0){
temp = Math.abs(left - i * average) + Math.abs((sum - left-arr[i])-((n-i-1)*average));
max = Math.max(max,temp);
}else{
temp = Math.max(Math.abs(left - i * average),Math.abs((sum - left-arr[i]) - ((n-i-1)*average)));
max = Math.max(max,temp);
}
left += arr[i];
}
return max;
}
public static void main(String[] args) {
int[] arr = {1,0,5};
System.out.println(machine(arr));
}
}
- 给定一个数组arr长度为N，你可以把任意长度大于0且小于N的前缀作为左部分，剩下的 作为右部分。
但是每种划分下都有左部分的最大值和右部分的最大值，请返回最大的， 左部分最大值减去右部分最大值的绝对值。 - 流程求数组中的最大值，然后减去0位置和i-1位置较小的那个一数。
/**
* 给定一个数组arr长度为N，你可以把任意长度大于0且小于N的前缀作为左部分，剩下的 作为右部分。
*
* 但是每种划分下都有左部分的最大值和右部分的最大值，请返回最大的， 左部分最大值减去右部分最大值的绝对值。
*/
public class ArrayOfMax {
public static int arrayOfMax(int[] arr){
// 假设输入参数有效
int n = arr.length;
int max = arr[0];
for (int i = 1; i < n; i++) {
max = Math.max(arr[i],max);
}
int temp = arr[0] > arr[n-1] ? arr[n-1] : arr[0];
return max - temp;
}
}
- 给定一个数组arr，已知其中所有的值都是非负的，将这个数组看作一个容器， 请返回容器能装多少水比如，arr = {3，1，2，5，2，4}，根据值画出的直方图就是容器形状，该容 器可以装下5格水再比如，arr = {4，5，1，3，2}，该容器可以装下2格水。
- 双指针，数组的头和尾不可能形成容器直接跳过，记录一个左边最大值，一个右边最大值，如果左小于右先结算左边水量，如果右小于左先结算右边的水量，哪边是瓶颈就先结算哪边的水量。
public class Water {
public static int water(int[] arr){
if(arr == null || arr.length == 0){
return 0;
}
int n = arr.length;
// 由于首尾都不能形成容器，多以不计算首位
// 一开始的左边最大就是0位置，右边最大就是n-1位置
int leftMax = arr[0];
int rightMax = arr[n-1];
int L = 1;
int R = n - 2;
int water = 0;
// 哪边的最大值是小先结算哪边（小的一边是瓶颈）
while (L <= R){
if(leftMax < rightMax){
// 结算左边
water += Math.max(0,leftMax - arr[L]);
leftMax = Math.max(leftMax,arr[L++]);
}else {
// 结算右边
water += Math.max(0,rightMax - arr[R]);
rightMax = Math.max(rightMax,arr[R--]);
}
}
return water;
}
public static void main(String[] args) {
int[] arr = {4,5,1,3,2};
System.out.println(water(arr));
}
}
- 如果给你一个二维数组，每一个值表示这一块地形的高度，
求整块地形能装下多少水。 - 利用小根堆求解。由于四个边都不能形成装水区域，首先把四个边加入到小根堆中，在准备一个布尔类型的二维数组，记录所有进过小根堆的位置，进过一次后就不允许在进入小根堆了。每次弹出一个元素然后收集他相邻的上下左右四个位置的水位，然后把四个位置放入下根堆，重复上述过程直到小根堆变为空。
/**
* 如果给你一个二维数组，每一个值表示这一块地形的高度，
* 求整块地形能装下多少水。
*/
public class HeapWater {
public static int heapWater(int[][] matrix){
if(matrix == null || matrix.length == 0){
return 0;
}
// 小根堆
PriorityQueue<Node> heap = new PriorityQueue<>(new MyComparator());
// 先把二维数组四个边加入到堆中
int rowNum = matrix.length;
int colNum = matrix[0].length;
boolean[][] flag = new boolean[rowNum][colNum];
for (int i = 0;i < colNum;i++){
// 上下两行
heap.offer(new Node(matrix[0][i],0,i));
heap.offer(new Node(matrix[rowNum-1][i],rowNum-1,i));
flag[0][i] = true;
flag[rowNum-1][i] = true;
}
for (int i = 1; i < rowNum-1; i++) {
// 左右两列
heap.offer(new Node(matrix[i][0],i,0));
heap.offer(new Node(matrix[i][colNum-1],i,colNum-1));
flag[i][0] = true;
flag[i][colNum-1] = true;
}
int max = 0;
int water = 0;
while (!heap.isEmpty()){
// 弹出元素收集上下左右的水
Node poll = heap.poll();
max = Math.max(max,poll.value);
// 进过小根堆的元素都是结算过得不要重复结算
if(poll.i-1>=0 &&!flag[poll.i-1][poll.j]){
water += Math.max(0,(max-matrix[poll.i-1][poll.j]));
heap.offer(new Node(matrix[poll.i-1][poll.j],poll.i-1,poll.j));
flag[poll.i-1][poll.j] = true;
}
if(poll.i+1 < rowNum && !flag[poll.i+1][poll.j]){
water += Math.max(0,(max-matrix[poll.i+1][poll.j]));
heap.offer(new Node(matrix[poll.i+1][poll.j],poll.i+1,poll.j));
flag[poll.i+1][poll.j] = true;
}
if(poll.j-1>=0 && !flag[poll.i][poll.j-1]){
water += Math.max(0,max-(matrix[poll.i][poll.j-1]));
heap.offer(new Node(matrix[poll.i][poll.j-1],poll.i,poll.j-1));
flag[poll.i][poll.j-1] = true;
}
if(poll.j+1<colNum && !flag[poll.i][poll.j+1]){
water += Math.max(0,(max-matrix[poll.i][poll.j+1]));
heap.offer(new Node(matrix[poll.i][poll.j+1],poll.i,poll.j+1));
flag[poll.i][poll.j+1] = true;
}
}
return water;
}
// 自定义比较器
static class MyComparator implements Comparator<Node>{
@Override
public int compare(Node o1, Node o2) {
return o1.value - o2.value;
}
}
public static void main(String[] args) {
int[][] martix = {
{4,4,4,4,4},
{4,1,4,1,4},
{4,2,4,3,4},
{4,4,4,4,4}
};
System.out.println(heapWater(martix));
}
}
public class Node {
// 横坐标
public int i;
// 纵坐标
public int j;
int value;
public Node(int value,int i,int j){
this.value = value;
this.i = i;
this.j = j;
}
}
- 给定一个有序数组arr，给定一个正数aim
1）返回累加和为aim的，所有不同二元组
2）返回累加和为aim的，所有不同三元组 - 双指针求解。定义双指针L和R,应为数组是有序的那么必然存在单调性，规定arr[L]+arr[R]和为S，当S>aim时向左移动R，当S小于aim时，向右移动R，当S等于aim时找到一个二元组。注意只有在L不等于L-1或者R不等R+1的情况下才收集答案，应为这种情况下收集到的答案是第一次遇到的二元组。
/**
* 给定一个有序数组arr，给定一个正数aim
* 1）返回累加和为aim的，所有不同二元组
* 2）返回累加和为aim的，所有不同三元组
*/
public class ErYaun {
// 返回二维数组每一行代表一个二元组，第一列代表二元组中第一个数
// 第二列代表二元组中第二个数
public static List<Yuan> erYuan(int[] arr, int aim){
if(arr == null || arr.length == 0){
return null;
}
int n = arr.length;
List<Yuan> res = new ArrayList<>();
// 定义双指针
int L = 0;
int R = n - 1;
while (L < R){
if(arr[L]+arr[R] < aim){
// L向右移动
L ++;
}else if(arr[L]+arr[R] > aim){
// R向左移动
R --;
}else{
if(L == 0 || arr[L] != arr[L-1]){
res.add(new Yuan(arr[L++],arr[R]));
}else{
L++;
}
}
}
return res;
}
// 三元，从头到尾遍历元素，当前位置i 用aim - arr[i] 看i+1开始有多少二元组达标aim-arr[i]
public static List<SanYuan> sanYuan(int[] arr,int aim){
if(arr == null || arr.length == 0){
return null;
}
int n = arr.length;
List<SanYuan> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
// 定义双指针,每次开头都会变化
int L = i + 1;
int R = n - 1;
int temp = aim - arr[i];
while (L < R){
if(arr[L]+arr[R] < temp){
// L向右移动
L ++;
}else if(arr[L]+arr[R] > temp){
// R向左移动
R --;
}else{
if(L == 0 || arr[L] != arr[L-1]){
res.add(new SanYuan(arr[i],arr[L++],arr[R]));
}else{
L++;
}
}
}
}
return res;
}
}
- 长度为N的数组arr，一定可以组成N^2个数值对。
例如arr = [3,1,2]，
数值对有(3,3) (3,1) (3,2) (1,3) (1,1) (1,2) (2,3) (2,1) (2,2)，
也就是任意两个数都有数值对，而且自己和自己也算数值对。
数值对怎么排序？规定，第一维数据从小到大，第一维数据一样的，第二维数组也从小到大。所以上面的数值对排序的结果为：
(1,1)(1,2)(1,3)(2,1)(2,2)(2,3)(3,1)(3,2)(3,3)
给定一个数组arr，和整数k，返回第k小的数值对。 - 假设数组有序，那么第K小的数值对的第一元素在原素组的下标其实可以算出来是index = k-1/n,根据第一维下标可以知道帮我们搞定了前面n(index)个，还有几个要搞定呢？-> k-(n(index))个，第二个下标就是求在大于等于index情况下找出（k-nindex）个的位置（k-nindex）/n
/**
* 长度为N的数组arr，一定可以组成N^2个数值对。
* 例如arr = [3,1,2]，
* 数值对有(3,3) (3,1) (3,2) (1,3) (1,1) (1,2) (2,3) (2,1) (2,2)，
* 也就是任意两个数都有数值对，而且自己和自己也算数值对。
* 数值对怎么排序？规定，第一维数据从小到大，第一维数据一样的，第二维数组也从小到大。所以上面的数值对排序的结果为：
* (1,1)(1,2)(1,3)(2,1)(2,2)(2,3)(3,1)(3,2)(3,3)
*
* 给定一个数组arr，和整数k，返回第k小的数值对。
*/
public class KSmall {
public static int[] kSmall(int[] arr,int k){
if(arr == null || arr.length == 0){
return null;
}
int n = arr.length;
if(k > n*n){
return null;
}
// 定位第一个坐标，如果数组长度为n,那么我们知道第一元素会帮我搞定n个数值对
// 第二个会帮我搞定n个数值对，所以我们可以得知如果求第k小那么在有序数组中
// 第一维小标一定在(k-1)/n的位置
int firstIndex = (k - 1) / n;
// 第二维元素求解，若我们已经知道了第一维的下标，那么小于这个小标的数的个数我们假设为a,等于这个下标位置数的个数为b
// a可以帮我们搞定a*n个，那么还剩下k-a*n个没搞定，一定是用等于等于这个下标的数字完成的有b个小标为(k-a*n) - 1/b
// 小于数量
int small = 0;
// 等于数量
int eq = 0;
// 利用parttion过程求无数数组中第k小问题
int r1 = process(arr,0,n-1,firstIndex);
for(int i = 0;i < n;i++){
if(arr[i] < r1){
small++;
}
if(arr[i] == r1) {
eq ++;
}
}
int r2 = process(arr,0,n-1,((k-small*n)-1)/eq);
return new int[]{r1,r2};
}
// 无序数组中求第k小的数，时间复杂度O(N)
private static int[] parttion(int[] arr,int L,int R,int aim){
// 小于区域
int less = L-1;
// 大于区域
int more = R+1;
int cur = L;
// 一次循环小于index位置数的进小于区域，
// 大于index 位置数的进大于区域
// 等于index位置数的不动
while (cur < more){
if(arr[cur] < aim){
// 进小于区域,跟小于区域下一个位置交换，小于区域向右扩一个位置
// 当前元素向前移动一个位置
swap(arr,cur++,++less);
}else if(arr[cur] > aim){
// 进大于区域，跟大于区域前一个交换，大于区域向左缩小一个位置
// 当前位置不变
swap(arr,cur,--more);
}else {
cur++;
}
}
// 最后放回等于L~R必定都是等于k位置的数
return new int[]{less+1,more-1};
}
private static int process(int[] arr,int L,int R,int k){
while (L <= R){
// 只会进一侧
int aim = arr[L + (int)(Math.random()*(R - L+1))];
int[] parttion = parttion(arr, L, R,aim);
if(k >= parttion[0] && k<=parttion[1]){
return arr[parttion[0]];
}else if(k < parttion[0]){
R = parttion[0]-1;
}else {
L = parttion[1]+1;
}
}
// 这一句不会执行
return 0;
}
private static void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
