问题：以尽量快的效率求出一个乱序数组中按数值顺序的第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>0int 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++;}}
}