算法随笔(快排,随机快排,归并排序,找中位数, 第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;
           }
   }
     }

        
        
    }

         


 

上一篇:分割数据预处理


下一篇:Seata分布式事务AT模式介绍(二)