算法随笔(快排,随机快排,归并排序,找中位数, 第k小元素问题 ,棋盘覆盖)
2021/6/16 20:26:25
本文主要是介绍算法随笔(快排,随机快排,归并排序,找中位数, 第k小元素问题 ,棋盘覆盖),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
快速排序import java.util.Scanner; public class Main { public static void change(int a[],int p,int q) { int t; t=a[p]; a[p]=a[q]; a[q]=t; } public static int partition(int a[],int p,int q) { int x=a[p]; int i=p,j; for(j=p+1;j<=q;j++) { if(a[j]<x) { i++; change(a,i,j); } } change(a,p,i); return i; } public static void quckSort(int a[],int p,int q) { if(p<q) { int x=partition(a,p,q); quckSort(a,p,x-1); quckSort(a,x+1,q); } } public static void main(String[] args){ Scanner cin=new Scanner(System.in); while(cin.hasNext()) { int n=cin.nextInt(); int a[]=new int[n]; for(int i=0;i<a.length;i++) { a[i]=cin.nextInt(); } quckSort(a,0,a.length-1); for(int i=0;i<a.length;i++) { System.out.print(a[i]+" "); } System.out.println(); } } }随机化快速排序
import java.util.Random; import java.util.Scanner; public class Main { public static void change(int a[],int p,int q) { int t; t=a[p]; a[p]=a[q]; a[q]=t; } public static int partition(int a[],int p,int q) { int x=a[p]; int i=p,j; for(j=p+1;j<=q;j++) { if(a[j]<x) { i++; change(a,i,j); } } change(a,p,i); return i; } int randomswap(int a[],int p,int q) { int k=(int) ((Math.random()% (q-p+1))+ q); change(a,k,p); return partition(a,p,q); } public static void quckSort(int a[],int p,int q) { if(p<q) { int k=partition(a,p,q); quckSort(a,p,k-1); quckSort(a,k+1,q); } } public static void main(String[] args){ Scanner cin=new Scanner(System.in); while(cin.hasNext()) { int n=cin.nextInt(); int a[]=new int[n]; for(int i=0;i<a.length;i++) { a[i]=cin.nextInt(); } quckSort(a,0,a.length-1); for(int i=0;i<a.length;i++) { System.out.print(a[i]+" "); } System.out.println(); } } }归并排序
import java.util.Scanner; import javax.swing.plaf.synth.SynthSpinnerUI; public class Main { static void Merge(int c[],int d[],int l,int m,int r){ int i=l; int j=m+1; int k=l; while(i<=m&&j<=r){ if(c[i]<c[j]){ d[k++]=c[i++]; } else{ d[k++]=c[j++]; } } if(i>m) for(int q=j;q<=r;q++){ d[k++]=c[q]; } else for(int q=i;q<=m;q++){ d[k++]=c[q]; } } static void mergePass(int x[],int y[],int lx,int ly,int s){ int i=0; while(i<=lx-2*s){ Merge(x,y,i,i+s-1,i+2*s-1); i=i+2*s; } if(i+s<lx){ Merge(x,y,i,i+s-1,lx-1); } else{ for(int j=i;j<lx;j++){ y[j]=x[j]; } } } static void mergeSort(int a[],int n){ int b[]=new int[n]; int s=1; while(s<n){ mergePass(a,b,n,n,s); s+=s; mergePass(b,a,n,n,s); s+=s; } } public static void main(String[] args) { Scanner cin=new Scanner(System.in); while(cin.hasNext()) { int n=cin.nextInt(); int a[]=new int[n]; for(int i=0;i<a.length;i++) { a[i]=cin.nextInt(); } mergeSort(a,n); for(int i=0;i<n;i++){ System.out.print(a[i]+" "); } System.out.println(); } }}找中位数
请设计一个算法,不排序,快速计算出一个无序数列的中位数。 时间复杂度要求为O(n)。
如果有奇数个元素,中位数则是数组排序后最中间的那个数字。
如果是偶数个元素,中位数则是数组排序后最中间两个元素的平均值。
输入
有多组输入,每组输入的第一行为n(1<=n<=1e5),表示该数列的元素个数。
第二行为n个整数组成的无序数列
输出
每组样例输出一行,表示该无序数列的中位数。
若为偶数,请保留三位小数
若为奇数,直接输出
样例输入 Copy
5
5 3 2 1 4
样例输出 Copy
3
思路:题目要求不可以使用排序来找中位数,
因此我们不可以排序来解题
中位数是指一段序列中,比它大的数和比它小的数的数量相等的那个数。序列经过排序后中位数在最中间。可以联想到使用快速排序的思想,找到最终位置在n/2的那个数。
中位数在数组中的索引为 (low+high)/2;
而且我们知道在快排中的partition函数可以将其数组分为一个数的左边比起小,右边比起大的形式。我们定义一个pos,如果等于mid,就证明已经找到,如果pos比mid大,说明则这个数比中位数大,又因为这个数右边的数都比这个数大,则可以high=pos-1,将这个数右边的数都舍去再进行快排。
import java.text.DecimalFormat; import java.util.Scanner; public class Main { public static void swap(int a[],int p,int q) { int t; t=a[p]; a[p]=a[q]; a[q]=t; } public static int partition(int a[],int p,int q) { int x=a[p]; int i=p,j; for(j=p+1;j<=q;j++) { if(a[j]<x) { i++; swap(a,i,j); } } swap(a,p,i); return i; } public static void getMid(int a[],int p,int q) { int mid=(p+q)/2; while(true) { int pos=partition(a,p,q); if(pos==mid)break; else if(pos>mid) {q=pos-1;} else {p=pos+1;} } if(a.length%2!=0) { System.out.println(a[mid]);} else { double MID=1.0*(a[mid]+a[mid+1])/2; System.out.println(String.format("%.3f", MID)); } } public static void main(String[] args) { Scanner cin = new Scanner(System.in); while(cin.hasNext()) { int n=cin.nextInt(); int a[]=new int[n]; for(int i=0;i<a.length;i++) { a[i]=cin.nextInt(); } getMid(a,0,a.length-1); } } }第k小元素问题
题目描述
输入一个整数数组,请求出该数组的第k小元素。要求时间复杂度为O(n)。
输入
每组输入包括两行,第一行为一个整数数组,两个数字之间用空格隔开;第二行为k值。数组中元素个数小于10^9。
输出
输出第k小元素的值。
样例输入 Copy
2 5 6 1 8 7 9
2
样例输出 Copy
2
思想:对于无序序列a[s…t],在其中查找第k小元素的过程:
若s=t,即其中只有一个元素,返回a[s]
若s!=t,表示该序列中有两个或两个以上元素,以基准为中心将其划分为a[s…i]和a[i+1…t],a[s…i]中所有元素均小于等于a[i],a[i+1…t]中所有元素均大于a[i]
j = i-s+1,统计小于等于a[i]的元素个数
j>=k,第k小元素在a[s…i]中,递归在a[s…i]中寻找第k小元素
j < k,第k小元素在a[i+1…t]中,递归在a[i+1…t]中寻找第k-j小元素
为了演示方便,我定义了数组的长度。
import java.text.DecimalFormat; import java.util.ArrayList; import java.util.Scanner; public class Main { public static void swap(int a[],int p,int q) { int t; t=a[p]; a[p]=a[q]; a[q]=t; } public static int partition(int a[],int p,int q) { int x=a[p]; int i=p,j; for(j=i+1;j<q;j++) { if(a[j]<x) { i++; swap(a,i,j); } swap(a,p,i); } return i; } static int quickSelect(int a[], int s, int t, int k) { if (s==t) return a[s]; int i= partition(a,s,t), j=i-s+1;//统计比k小的元素个数 if (k<=j) return quickSelect(a, s, i, k); else return quickSelect(a, i+1, t, k-j); } public static void main(String[] args) { Scanner cin = new Scanner(System.in); int n=cin.nextInt(); int a[]=new int[n]; for(int i=0;i<n;i++) { a[i]=cin.nextInt(); } int k=cin.nextInt();//第k小的数 System.out.println(quickSelect(a,0,n-1,k)); } }棋盘覆盖问题
题目描述
在一个n×n (n = 2k)个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。
在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
输入
多组测试用例,每组测试用例包括两部分,
第一部分为方格的宽度n,
第二部分则为方格,特殊方格为-1,其他方格为0。
输出
输出覆盖后的方案
样例输入 Copy
4
-1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
样例输出 Copy
-1 2 4 4
2 2 1 4
3 1 1 5
3 3 5 5
1.分割棋盘:将大棋盘分割为四个小棋盘
2.判断特殊方格的位置:判断特殊方格在哪个小棋盘中
3.判断方法:记录大棋盘左上角方格的行列坐标,结合棋盘边长再与特殊方格的坐标进行比较,可判断特殊方格的位置
4.如果特殊方格在某一小棋盘中,继续递归
5.如果不在某一小棋盘中,则根据分割的四个小棋盘的不同位置,把右下角、左下角、右上角或者左上角的方格标记为特殊方格,然后继续递归
变量s用于记录边的方格数(边长),每次对棋盘进行分割时,边的方格数都会减半
import java.text.DecimalFormat; import java.util.ArrayList; import java.util.Scanner; public class Main { //tr表示棋盘左上角行号 //tc表示棋盘左上角列号 //dr表示特殊棋盘的行号 //dc表示特殊棋盘的列号 //size = 2^k //棋盘的规格为2^k * 2^k static int x,y;//标记特殊方块的位置 static int tile=1; static int board[][]=new int[8][8]; static void chessBoard(int tr, int tc, int dr, int dc, int size) { if (size == 1) return; int t = tile++, // L型骨牌号 s = size/2; // 分割棋盘 // 覆盖左上角小棋盘 if (dr < tr + s && dc < tc + s) // 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s); else {// 此棋盘中无特殊方格 // 用 t 号L型骨牌覆盖右下角 board[tr + s - 1][tc + s - 1] = t; // 覆盖其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s);} // 覆盖左下角小棋盘 if (dr >= tr + s && dc < tc + s) // 特殊方格在此棋盘中 chessBoard(tr+s, tc, dr, dc, s); else {// 用 t 号L型骨牌覆盖右上角 board[tr + s][tc + s - 1] = t; // 覆盖其余方格 chessBoard(tr+s, tc, tr+s, tc+s-1, s);} // 覆盖右上角小棋盘 if (dr < tr + s && dc >= tc + s) // 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else {// 此棋盘中无特殊方格 // 用 t 号L型骨牌覆盖左下角 board[tr + s - 1][tc + s] = t; // 覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s);} // 覆盖右下角小棋盘 if (dr >= tr + s && dc >= tc + s) // 特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s); else {// 用 t 号L型骨牌覆盖左上角 board[tr + s][tc + s] = t; // 覆盖其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s);} } public static void main(String[] args) { Scanner cin = new Scanner(System.in); int n=cin.nextInt(); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { board[i][j]=cin.nextInt(); } }//输入数据 //寻找特殊的方格 for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(board[i][j]==-1) { x=i; y=j; } } } chessBoard(0,0,x,y,n); for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { System.out.print(board[i][j]+" "); } System.out.println(); } //初始化 tile=1; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { board[i][j]=0; } } } }
这篇关于算法随笔(快排,随机快排,归并排序,找中位数, 第k小元素问题 ,棋盘覆盖)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?