蓝桥杯算法基础（21）：（6道小题：奇数在左，第k个元素,超过一半的数字，最小可用ID，合并有序数组，逆序对个数）java版
题1:奇数在左
调整数组顺序使奇数位于偶数前面:输入一个整数数组，调整数组中数字的顺序，是的所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为o(n).
1.可以用快排的思想，用双指针，左指针找偶数，右指针找奇数，两者交换，直到左右指针交叉 static void Sort1(int[] arr,int length){ int left=0; int right=length-1; while(left<=right){ while(arr[left]%2==1)left++; while(arr[right]%2==0)right--; Util.swap(arr,left,right); } }2.可以利用辅助空间，奇数放到左边，偶数放到右边 不过复杂度高一点
第k个元素
以尽量高的效率求出一个乱序数组中按数值顺序的第k个元素值
（伪代码）
selectK(A,p,r,k){
q=partition(A,p,r);//主元的下标
qK=q-p+1;//主元是第几个元素
if(qK==k)
return A[q];
else if(qK>k){
return selectK(A,p,q-1,k);
else return selectK(A,p+1,q,k-qK);//若是选右边，K需要有所变化，中间开始算第一个，k-qK找的是第k-qK而不是下标
}
}
partition(A,p,r);//快排求主元，将小于等于主元的放到数组左边，大于主元的放到右边
超过一半的数字
数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。
解法1:排序后返回arr[N/2]
static void solve1(int[] arr){
Arrays.sort(arr);
System.out.println(arr.length/2);
}
解法2:hash统计（计数）
static void solve2(int[] arr){
int maxcount=0,max=0;
int arr1[arr.length];//默认值为0
for(int i=0;i<arr.length;i++)
arr1[arr[i]]++;
for(int i=0;i<arr.length;i++)
{ if(arr1[i]==0)continue;
if(arr1[i]>maxcunt)
{maxdount=arr1[i];
max=i;
}
}
System.out.println(max);
}
解法3:顺序统计
static void solve3(int[] arr){
int res=Case02_Orderstatistic.selectK(arr,0,length-1,arr.length/2);
//延续上一题第k个元素直接找位于中间的值
}
解法4:不同的数，进行消除
static void solve4(int[] arr){
int x=arr[0];
for(int i=1;i<arr.length;i++)
if(x!=arr[i])
{i++;
x=arr[i];
}
System.out.println(x);
}
改一下题
若是某一个数刚好是数组的一半，求这个数
用解法4，不同的数，进行消除
相比解法4的简单消除不同，需要一些变化
有可能出现1 a 2 a 3 a 4 a 5 a
这种情况，结果肯定在最后两个数中
设立一个变量count，我们遍历时，每一个数都要与最后一个数比较，若相等，则加1
遍历结束后，若是变量count=length/2,则为最后一个，否则为倒数第二个
最小可用ID
在非负数组(乱序)中找到最小的可分配的id(从1开始编号)，数据量1000000
//暴力解法:从1开始一次探测每个自然数是否在数组中
static int find1(int[] arr){
int i=1;
while(true){
if(Util.indexOf(arr,i)==-1){
return i;}
i++;
}
}
static void find2(int[] arr){
Arrays.Sort(arr);
int i=0;
while(i<arr.length){//也可以用二分查找
if(i+1!=arr[i]){//不在位的最小的自然数
return i+1;
}
i++;
}
return i+1;
}
可以用辅助空间，若是该数字出现，该下标所在辅助空间为1
public static void int find3(int[] arr){
int n=arr.length;
int[] helper=new int[n+1];//若是中间有断开，超过length长度的值就不用考虑了
for(int i=1;i<n;i++){
if(arr[i]<n+1)
helper[arr[i]]=1;
}
for(int i=0;i<=n;i++){
if(helper[i]==0){
return i;}
}
return n+1;//没找到，返回length+1
}
也可以用快排，找主元，如果主元所在位置不顺序不符，则结果在左侧，若是相符，在结果在右侧，继续找主元即可
public static void find4(int[] arr,int i,int r){
if(l>r)
return l+1;//最后结束，r与l交叉，为左侧元素紧密为r所指，右侧元素不紧密为l所指，因为从1开始所以要下标加1
int midIndex=1+((r-l)>>1);//中间下标
int q=Case02_OrderStatistic.selectK(arr,l,r,midIndex-l+1);//实际在中间的值
//快排的找主元
int t=midIndex+1;
if(q==t){//左侧紧密
return find4(arr,midIndex+1,r);
else{
return find4(arr,l,midIndex-1);
}
}
}
合并有序数组
给定两个排序后的数组A和B，其中A的末端有足够的缓冲空间容纳B。编写一个方法，将B合并入A并排序
A 1 2 3 4 6 8 12
| |
B 2 5 7
|
三个指针，进行归并，谁大谁放到A后面从A.length+B.length-1开始
static void mergeAandB(int[] A,int[] B){
int i=A.length-1;
int j=B.length-1;
int s=A.length+B.length-1;
while(i>=&&j>=0){
if(A[i]<=B[j]){
A[s--]=B[j--];
}else{
A[s--]=A[i--];
}
}
while(j>=0){A[s--]=B[j--];}
}
逆序对个数
一个数列，如果左边的数大，右边的数小，则称着两个数为一个逆序对。求出一个数列中有多少个逆序对
private static void sort(int[] A,int p,int r){
if(p<r){
int mid=p+((r-o)>>1);
sort(A,p,mid);//对左侧排序
sort(A,mid+1;r);//对右侧排序
merge(A,p,mid,r);//合并
}
}
//归并排序的合并部分
private static void merge(int[] A,int p,int mid,int r){
//拷贝到辅助空间的相同位置
System.arraycopy(A,p,helper,p,r-p+1);
//辅助数组的两个指针
int left=p,right=mid+1;
//原始数组的指针
int current=p;
while(left<=mid&&right<==r){
if(helper[left]<=helper[right]){
A[current++]=helper[left++];
}else{//右边小，因为左右已经排好序，3 6 8， 4 5 7->3 4(右边小，也就是说，左侧部分内还有6和8比放入的这个右边的数大，因此逆序增加2)
A[current++]=helper[right++];
niXu=mid-left+1;//归并排序的一部分，属于合并部分，左右两部分已经排好序了
//niXu为全局变量
}
}
while(left<=mid){
A[current]=helper[left];
current++;
left++;
}
}