问题：以尽量快的效率求出一个乱序数组中按数值顺序的第k小的元素。
解法一：先用快排进行排序，然后在找到第k+1个元素，时间复杂度为nlg(n)
解法二：用快排划分为俩个子序列，找到主元素的下标,该下标+1=x即为主元素在该数组的第x小元素，判断k与x的大小缩小范围，时间复杂度期望O(n),最差O(n^2)
下面只说了解法二：
public class Test2 {
public static void main(String[] args) {
int[] arr = new int[]{2,4,5,6,7,1,9,8,3};
System.out.println(f2(arr,6,0,arr.length-1));
}
static int f2(int[] arr,int k,int p,int r){
int q = partition(arr,p,r); //此时q前面的数都比q小，后面的数都比q大，所以该数为第q+1大的数
if(q-p < k-1){
return f2(arr,k-1-q+p,q+1,r);
}else if(q-p > k-1){
return f2(arr,k,p,q-1);
}else{
return arr[q];
}
}
//双向扫描，快排
static int partition(int[] arr,int p,int r){
int pivot=arr[p];
int left=p+1;
int right=r;
while(left<=right){
while(left<=right && arr[left]<=pivot) left++;
while(left<=right && arr[right]>pivot) right--;
if(left<right)
swap(arr,left,right);
}
swap(arr,p,right);
return right;
}
static void swap(int[] arr,int l,int r) {
int t = arr[l];
arr[l] = arr[r];
arr[r] = t;
}
}问题：找出无序数组中出现次数超过一半的元素
方法一： 排序后，中间下标元素就是我们要找的,时间复杂度nlg(n)
方法二： 顺序统计，数组长度为n，求第n/2大的元素，时间复杂度：n
方法三： 数不相同count就减一，count为0就改变cur值，最后一定只有出现次数最多的元素的count>0
但如果不允许挪动数组中元素的位置呢？
方法三：
public class Test2 {
public static void main(String[] args) {
int[] arr = new int[]{2,4,5,6,7,1,9,8,3};
System.out.println(f2(arr,6,0,arr.length-1));
}
static int f3(int[] arr){
//方法三 数不相同count就减一，count为0就改变cur值，最后一定只有出现次数最多的元素的count>0
int cur=arr[0],count=1;
for(int i=1;i<arr.length;i++){
if(cur != arr[i]){
count--;
}else{
count++;
}
if(count==0){
cur=arr[i];
count=1;
}
}
return cur;
}
}那此题目，在不允许挪动数组中元素的位置的情况下，缩小次数，出现次数最多的元素的出现次数恰好为数组长度的一半呢?
解决：在方法三的基础上加点条件即可：新增无序数组中最后一个元素的计数器
如果最后一位为所求元素，遍历完后，最后一个元素的计数器的值一定为数组长度的一半。
如果最后一位不为所求元素，当要遍历最后一个元素时，
此时方法三中的count值一定为1，因为如果不算最后一个元素的话，满足所求元素出现次数超过数组长度一半，所以此时cur值一定为所求元素。
然后因为最后一个元素的计数器的值不为数组长度的一半，所以cur值即为所求
public class Test2 {
public static void main(String[] args) {
int[] arr = new int[]{2,4,5,6,7,1,9,8,3};
System.out.println(f2(arr,6,0,arr.length-1));
}
static int f4(int[] arr) {
int cur=arr[0],count=0;
int countLast=0,lastNum=arr[arr.length-1];
for(int i=0;i<arr.length;i++) {
if (cur != arr[i]) {
count--;
} else {
count++;
}
if (arr[i] == lastNum) {
countLast++;
}
if (i == arr.length - 1) {
if (countLast == arr.length / 2) {
return lastNum;
} else {
return cur;
}
}
if (count == 0) {
cur = arr[i];
count=1;
}
}
return cur;
}
}问题：最小可用ID：在非负数组（乱序）中找到最小可分配的id（从1开始编号），数据量1000000。
就是在乱序数组（数组大小不超过1000000）中找出最小的从未出现过的数（1～1000000）。
解法一：开辟一个等大+1的数组helper，遍历一遍原数组，在helper相应位置打上标记，然后遍历一遍helper，时间复杂度2n；
public class Test2 {
public static void main(String[] args) {
int[] arr = new int[]{3,4,5,1,6,7,8,13,9,27,40,20,2};
System.out.println(f1(arr));
}
static int f1(int[] arr){
int[] helper = new int[arr.length+1];
for(int i=0;i<arr.length;i++){
if(arr[i]<=arr.length){ //如果有元素大于数组长度，说明1～arr.length之间一定不连续，所求的数在该范围内。
helper[arr[i]]++;
}
}
for(int i=1;i<helper.length;i++){
if(helper[i]!=1)
return i;
}
return helper.length;
}
}解法二：不采用辅助空间，采用求第k小元素的方法
选取一个元素作为主元素，判断主元素的值是否等于其下标值，若等于，则所求在右侧，若主元素值大于其下标则所求在左侧，主元素值不可能小于下标值
public class Test2 {
public static void main(String[] args) {
int[] arr = new int[]{3,4,5,1,6,7,8,13,9,27,40,20,2};
System.out.println(f2(arr,0,arr.length-1));
}
static int f2(int[] arr,int p,int r){
if(p>=r)return p+2; //p为小于所求数的最大数的下标，p+1为所求数的下标，p+2为所求数
int partition = partition(arr, p, r);
if(partition +1< arr[partition]){
return f2(arr,p,partition-1);
}else {
return f2(arr,partition+1,r);
}
}
static int partition(int[] arr,int p,int r){
int pivot=arr[p];
int left=p+1;
int right=r;
while(left<=right){
while(left<=right && arr[left]<=pivot)left++;
while(left<=right && arr[right]>pivot)right--;
if(left<right)
swap(arr,left,right);
}
swap(arr,p,right);
return right;
}
static void swap(int[] arr,int l,int r) {
int t = arr[l];
arr[l] = arr[r];
arr[r] = t;
}
} 问题：一个数列，如果左边数大，右边数小，则称这俩个数位为一个逆序对，求一个数列中有多少个逆序对
比如：2 5 1 3 4中逆序对有 2、1 ； 5，1 ；5，3 ；5，4
解法：类似于归并数组，把数组前后分为俩部分，然后不断细分，直到剩俩个元素，然后升序排序，然后在对俩部分数组a(前半部分)，b(后半部分)中第一个数进行比较，如果b小，那么b数列中的这个元素拥有a数组中元素个数 个逆序对 ，每次比较取走最小的。
public class Test2 {
public static void main(String[] args) {
int[] arr = new int[]{2,6,7,8,9,3,1,4,5};
helper = new int[arr.length];
System.out.println(f4(arr));
}
static int f4(int[] arr){
sort1(arr,0,arr.length-1);
return niXuCount;
}
static void sort1(int[] arr,int low,int high){
if(low<high){
int mid = low+((high-low)>>1);
sort1(arr,low,mid);
sort1(arr,mid+1,high);
merge1(arr,low,mid,high);
}
}
static int[] helper;
static int niXuCount=0;
static void merge1(int[] arr,int low,int mid,int high){
//把arr中数据拷贝到helper中
for(int i=low;i<=high;i++){
helper[i]=arr[i];
}
int left =low; //左侧队伍的头指针，指向待比较的元素
int right =mid+1; //右侧队伍的头指针，指向待比较的元素
int current=low; //原数组指针，指向待填入元素的位置
while(left<=mid && right<=high){ //俩个队伍都没走完
if(helper[left]<=helper[right]){
arr[current]=helper[left];
left++;
}else{
arr[current]=helper[right];
right++;
niXuCount+=mid+1-left; //此时前半部分数组的大小
}
current++;
}
while(left<=mid){
arr[current]=helper[left];
left++;
current++;
}
while(right<=mid){
arr[current]=helper[right];
right++;
current++;
}
}
}问题：给定一个无序数组arr，求出需要排序的最短子数组长度 来让原数组为升序，如 arr={2,3,7,5,4,6},返回4，需要排序7，5，4，6 这4个元素
解法：我们需要的数组是升序的，我们定义俩个端点p1，p2表示需要排序范围的左右端点。
我们先看怎么定义范围的右端点，只要当前元素值小于前面任意一个元素那么此元素就需要排序，
同样左端点，只要当前元素大于其后面的任意一个元素那么此元素就需要排序。
所以右端点从前往后遍历，数组应为升序，定义一个目前最大值，遍历过程中只要出现小于目前最大值的元素，右端点就扩展到此处。
左端点从后往前遍历，数组应为降序，定义一个目前最小值，遍历过程中只要出现大于目前最小值的元素，左端点就扩展到此处。
public class Test2 {
public static void main(String[] args) {
}
static int f2(int[] arr){
int p1=-1;//范围左端点
int p2=-1;//范围右端点
int max=arr[0]; //目前最大值，从前往后遍历，因为从前往后遍历，需要数组是升序的，只要后面的元素小于前面的，那么排序范围的右端就扩展到这
int min=arr[arr.length-1]; //目前最小值，从后往前遍历，需要数组是降序的，只要前面的元素大于后面的，那么排序范围的左端就扩展到这
//右端点：更新历史最高，只要右侧出现比历史最高小的数，就扩展到此处
for(int i=0;i<arr.length;i++){
max=Math.max(max,arr[i]);
//只要低于历史高峰，就要扩展排序范围
if(arr[i]<max) p2=i;
}
//左端点： 更新历史最低，只要左侧出现比历史最低大的数，就扩展到此处
for(int i=arr.length-1;i>=0;i--) {
min = Math.min(min, arr[i]);
if (arr[i] > min) p1 = i;
}
if(p1==-1)return 0;
return p2-p1+1;
}
}将无序数组改为升序的最小范围知道了，那么改为降序呢？
同样的去找俩个端点，右端点，从前往后遍历，应为降序，所以定义一个目前最小值，只要后面的元素大于目前最小值，右端点就扩展到此处； 左端点，从后往前遍历，应为升序，所以定义一个目前最大值，只要前面元素小于目前最大值，左端点就扩展到此处
public class Test2 {
public static void main(String[] args) {
}
static int f3(int[] arr){
int p1=-1,p2=-1;
int min=arr[0];
int max=arr[arr.length-1];
//右端点：更新历史最低，只要右侧出现比历史最低 大的数，就扩展到此处
for(int i=0;i<arr.length;i++){
/*if(i<arr.length-1 && arr[i]>arr[i+1] && p1==-1){ //找到第一个开始降的顶点
p1=i;
}*/
min=Math.min(min,arr[i]);
//只要低于历史高峰，就要扩展排序范围
if(arr[i] > min) p2=i;
}
//左端点： 更新历史最高，只要左侧出现比历史最高 小的数，就扩展到此处
for(int i=arr.length-1;i>=0;i--) {
max = Math.max(max, arr[i]);
if (arr[i] < max) p1 = i;
}
if(p1==-1)return 0;
return p2-p1+1;
}
}那么给定一个无序数组arr，求出需要排序的最短子数组长度 来让原数组有序，无论升降序呢？
public class Test2 {
public static void main(String[] args) {
int[] arr = new int[]{2,3,7,4,1,5,6};
System.out.println(f4(arr));
}
static int f2(int[] arr){
int p1=-1;//范围左端点
int p2=-1;//范围右端点
int max=arr[0]; //目前最大值，从前往后遍历，因为从前往后遍历，需要数组是升序的，只要后面的元素小于前面的，那么排序范围的右端就扩展到这
int min=arr[arr.length-1]; //目前最小值，从后往前遍历，需要数组是降序的，只要前面的元素大于后面的，那么排序范围的左端就扩展到这
//右端点：更新历史最高，只要右侧出现比历史最高小的数，就扩展到此处
for(int i=0;i<arr.length;i++){
max=Math.max(max,arr[i]);
//只要低于历史高峰，就要扩展排序范围
if(arr[i]<max) p2=i;
}
//左端点： 更新历史最低，只要左侧出现比历史最低大的数，就扩展到此处
for(int i=arr.length-1;i>=0;i--) {
min = Math.min(min, arr[i]);
if (arr[i] > min) p1 = i;
}
if(p1==-1)return 0;
return p2-p1+1;
}
static int f3(int[] arr){
int p1=-1,p2=-1;
int min=arr[0];
int max=arr[arr.length-1];
//右端点：更新历史最低，只要右侧出现比历史最低 大的数，就扩展到此处
for(int i=0;i<arr.length;i++){
/*if(i<arr.length-1 && arr[i]>arr[i+1] && p1==-1){ //找到第一个开始降的顶点
p1=i;
}*/
min=Math.min(min,arr[i]);
//只要低于历史高峰，就要扩展排序范围
if(arr[i] > min) p2=i;
}
//左端点： 更新历史最高，只要左侧出现比历史最高 小的数，就扩展到此处
for(int i=arr.length-1;i>=0;i--) {
max = Math.max(max, arr[i]);
if (arr[i] < max) p1 = i;
}
if(p1==-1)return 0;
return p2-p1+1;
}
static int f4(int[] arr){
return Math.min(f2(arr),f3(arr));
}
}输入一个正整数数组，把数组中所有数拼接成一个数，打印其中最小的那个
输入数组{3,32,321} 输出321323
static int f3(Integer[] arr){
Arrays.sort(arr, new Comparator<Integer>() {
@Override //自定义比较器规则
public int compare(Integer o1, Integer o2) {
String s1 = o1+""+o2;
String s2 = o2+""+o1;
return s1.compareTo(s2); //升序
}
});
StringBuilder sb = new StringBuilder();
for (Integer integer : arr) {
sb.append(integer);
}
return Integer.parseInt(sb.toString());
}