蓝桥杯算法基础(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++; } }