基础算法例题和模板（上）

• 快速排序

  • 题目描述

    给定你一个长度为 n 的整数数列。

    请你使用快速排序对这个数列按照从小到大进行排序。

    并将排好序的数列按顺序输出。

    输入格式

    输入共两行，第一行包含整数 nn。

    第二行包含 n个整数（所有整数均在 1∼1e+10 范围内），表示整个数列。

    输出格式

    输出共一行，包含 n 个整数，表示排好序的数列。

    数据范围

    1≤n≤100000

    输入样例：

    5
    3 1 2 4 5
    

    输出样例：

    1 2 3 4 5
    

  • 题解

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    public class AcWing785 {
        public static void main(String[] args) throws IOException {
            BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
            int n=Integer.parseInt(reader.readLine());
            int qian[]=new int[n];
            String[] strings=reader.readLine().split(" ");
            for (int i = 0; i < strings.length; i++) {
                qian[i]=Integer.parseInt(strings[i]);
            }
            quickSort(qian,0,n-1);
            for (int i = 0; i < qian.length; i++) {
                System.out.print(qian[i]+" ");
            }
        }
        public static void quickSort(int[] q,int l,int r){
            if(l>=r){
                return;
            }
            int i=l-1,j=r+1,x=q[l+r>>1];
            while (ix);
                if (i 

• 第k个数

  • 题目

    给定一个长度为 nn的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k个数。

    输入格式

    第一行包含两个整数 n和 k。

    第二行包含 n 个整数（所有整数均在 1∼1e+9 范围内），表示整数数列。

    输出格式

    输出一个整数，表示数列的第 k小数。

    数据范围

    1≤n≤100000
    1≤k≤n

    输入样例：

    5 3
    2 4 1 5 3
    

    输出样例：

    3
    

  • 题解

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    public class AcWing786 {
        static int[] qian;
        public static void main(String[] args) throws IOException {
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            String[] strings = reader.readLine().split(" ");
            int n = Integer.parseInt(strings[0]);
            int k = Integer.parseInt(strings[1]);
            qian = new int[n];
            String[] strings1 = reader.readLine().split(" ");
            for (int i = 0; i < qian.length; i++) {
                qian[i] = Integer.parseInt(strings1[i]);
            }
            int i = quickSortFind(0, n - 1, k);
            System.out.println(i);
        }
        public static int quickSortFind(int l, int r, int k) {
            if (l == r) {
                return qian[l];
            }
            int x = qian[l], i = l - 1, j = r + 1;
            while (i < j) {
                while (qian[++i] < x) ;
                while (qian[--j] > x) ;
                if (i < j) {
                    int temp;
                    temp = qian[i];
                    qian[i] = qian[j];
                    qian[j] = temp;
                }
            }
            int sl = j - l + 1;
            if (k <= sl) {
                return quickSortFind(l, j, k);
            } else {
                return  quickSortFind(j + 1, r, k - sl);
            }
        }
    }
    

快速排序要注意x取值的边界情况。取x = nums[left], nums分为[left, j]和[j + 1, right]，或x = nums[right], nums分为[left, i - 1]和[i, right],否则会StackOverflow。

public static void quickSort(int[] q,int l,int r){
        if(l>=r){
            return;
        }
        int i=l-1,j=r+1,x=q[l+r>>1];
        while (ix);
            if (i 
 
理解
 
  
 
   
基本思想 ：分治
 
   
通过一趟排序把将要排序的数据分成两个独立的部分，其中一个部分必然小于另一个部分，然后再按照这个方法将两个部分快速排序，整个过程可以递归，最后变成最终有序的数据
 
  
 
 
归并排序 
例题1 
 
归并排序
 
  
 
题目描述
 
 
    
 
     
给定你一个长度为 n的整数数列。
 
     
请你使用归并排序对这个数列按照从小到大进行排序。
 
     
并将排好序的数列按顺序输出。
 
     输入格式 
     
输入共两行，第一行包含整数 n。
 
     
第二行包含 n 个整数（所有整数均在 1∼1e+10范围内），表示整个数列。
 
     输出格式 
     
输出共一行，包含 n个整数，表示排好序的数列。
 
     数据范围 
     
1≤n≤100000
 
     输入样例： 
     
5
3 1 2 4 5
 
     输出样例： 
     
1 2 3 4 5
 
    
 
 
题解
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class AcWing787 {
    static int[] q;
    static int[] tmp;
    public static void main(String[] args) throws IOException {
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(reader.readLine());
        String[] strings=reader.readLine().split(" ");
        q=new int[n];
        tmp=new int[n];
        for (int i = 0; i < strings.length; i++) {
            q[i]=Integer.parseInt(strings[i]);
        }
        mergeSort(q,0,n-1);
        for (int i = 0; i = r) {
            return;
        }
        int mid=l+r>>1;
        mergeSort(q,l,mid);
        mergeSort(q,mid+1,r);
        int k=0,i=l,j=mid+1;
        while (i<=mid && j<=r){
            if(q[i]<=q[j]) tmp[k++]=q[i++];
            else tmp[k++]=q[j++];
        }
        while (i<=mid) tmp[k++]=q[i++];
        while (j<=r)   tmp[k++]=q[j++];
        for(i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
    }
}
 
 
 
例题2 
 
逆序对的数量
 
  
 
题目描述
 
    
 
     
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
 
     
逆序对的定义如下：对于数列的第 i个和第 j个元素，如果满足 ia[j]，则其为一个逆序对；否则不是。
 
     输入格式 
     
第一行包含整数 n，表示数列的长度。
 
     
第二行包含 n个整数，表示整个数列。
 
     输出格式 
     
输出一个整数，表示逆序对的个数。
 
     数据范围 
     
1≤n≤100000
 数列中的元素的取值范围
 
    
 
    
 
     输入样例： 
     
6
2 3 4 5 6 1
 
     输出样例： 
     
5
 
    
 
 
题解
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class AcWing788 {
    static int[] qian;
    static int[] tmp;
    public static void main(String[] args) throws IOException {
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(reader.readLine());
        String[] strings=reader.readLine().split(" ");
        qian=new int[n];
        for (int i = 0; i < qian.length; i++) {
            qian[i]=Integer.parseInt(strings[i]);
        }
        long l = mergeSort(0, n - 1);
        System.out.println(l);
        reader.close();
    }
    private static long mergeSort(int l, int r) {
        // 递归结束, 只有一个元素, 逆序对为 0
        if (l >= r) return 0;
        int mid = l + r >> 1;
        long res = 0;
        // 情况一和情况二, 并对左右数组进行排序
        res += mergeSort(l, mid) + mergeSort(mid + 1, r);
        // 归并排序
        tmp = new int[r - l + 1];
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            if (qian[i] <=qian[j]) tmp[k++] =qian[i++];
            else {
                tmp[k++] = qian[j++];
                // 情况三
                res += mid - i + 1;
            }
        }
        // 扫尾
        while (i <= mid) tmp[k++] = qian[i++];
        while (j <= r) tmp[k++] = qian[j++];
        // tmp -> arr
        for (i = l, j = 0; i <= r; i++, j++) {
            qian[i] = tmp[j];
        }
        return res;
    }
}
 
 
 
归并排序模板 
 
 
mergeSort时间复杂度是稳定O(nlogn)，空间复杂度O(n)，稳定的。quickSort时间复杂度平均O(nlogn)，最坏O(n^2)，最好O(nlogn)，空间复杂度O(nlogn)，不稳定的。
 
 
public void mergeSort(int[] nums, int left, int right) {
    if (left >= right)
        return;
    int mid = left + (right - left) / 2;
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);
    int k = 0, i = left, j = mid + 1;
    int[] temp = new int[right - left + 1];
    while (i <= mid && j <= right)
        if (nums[i] < nums[j])
            temp[k++] = nums[i++];
        else
            temp[k++] = nums[j++];
    while (i <= mid)
        temp[k++] = nums[i++];
    while (j <= right)
        temp[k++] = nums[j++];
    for (i = left, j = 0; i <= right; i++, j++)
        nums[i] = temp[j];
}
 
二分 
例题1 
 
数的范围
 
  
 
题目描述
 
    
 
     
给定一个按照升序排列的长度为 n的整数数组，以及 q 个查询。
 
     
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
 
     
如果数组中不存在该元素，则返回 -1 -1。
 
     输入格式 
     
第一行包含整数 n和 q，表示数组长度和询问个数。
 
     
第二行包含 n个整数（均在 1∼10000范围内），表示完整数组。
 
     
接下来 q 行，每行包含一个整数 k，表示一个询问元素。
 
     输出格式 
     
共 q行，每行包含两个整数，表示所求元素的起始位置和终止位置。
 
     
如果数组中不存在该元素，则返回 -1 -1。
 
     数据范围 
     
1≤n≤100000
 1≤q≤10000
 1≤k≤10000
 
     输入样例： 
     
6 3
1 2 2 3 3 4
3
4
5
 
     输出样例： 
     
3 4
5 5
-1 -1
 
    
 
 
题解
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class AcWing789 {
    static int n,m;
    public static void main(String[] args) throws IOException {
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        String[] strings=reader.readLine().split(" ");
        n=Integer.parseInt(strings[0]);
        m=Integer.parseInt(strings[1]);
        int[] qian=new int[n];
        String[] strings1=new String[100000];
        strings1=reader.readLine().split(" ");
        for (int i = 0; i 0){
            int x;
            x=Integer.parseInt(reader.readLine());
            int l=0,r=n-1;
            while (l>1;
                if(qian[mid]>=x){
                    r=mid;
                }else {
                    l=mid+1;
                }
            }
            if(qian[l]!=x){
                System.out.println("-1 -1");
            }else {
                System.out.print(l+" ");
                l=0;
                r=n-1;
                while (l>1;
                    if (qian[mid]<=x){
                        l=mid;
                    }else {
                        r=mid-1;
                    }
                }
                System.out.println(l);
            }
        }

    }
}
 
 
 
例题2 
 
数的三次方根
 
 
浮点数二分的本质也是边界, 唯一区别是浮点数没有整除, 区间长度可以严格的缩小一半,当区间长度足够小时, 便可以认为是一个数
 
  
 
题目描述
 
    
 
     
给定一个浮点数 n，求它的三次方根。
 
     输入格式 
     
共一行，包含一个浮点数 n。
 
     输出格式 
     
共一行，包含一个浮点数，表示问题的解。
 
     
注意，结果保留 6 位小数。
 
     数据范围 
     
−10000≤n≤10000
 
     输入样例： 
     
1000.00
 
     输出样例： 
     
10.000000
 
    
 
 
题解
 
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class AcWing790 {
    public static void main(String[] args) throws IOException {
       BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
       double target=Double.parseDouble(reader.readLine());
       double l=-10000,r=10000;
       for(int i = 0; i < 100; i++) {
            double mid=(l+r)/2;
            if (mid*mid*mid>=target){
                r=mid;
            }else {
                l=mid;
            }
        }
        System.out.printf("%6f",l);
    }
}
 
 
 
二分模板 
二分模板一共有两个，分别适用于不同情况。
算法思路：假设目标值在闭区间[l, r]中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。
 
版本1 
当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。
 
// 判断条件很复杂时用check函数，否则if后直接写条件即可
bool check(int mid) {
    ...
    return ...;
}

int bsearch1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}
 
版本2 
当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。
 
// 判断条件很复杂时用check函数，否则if后直接写条件即可
bool check(int mid) {
    ...
    return ...;
}

int bsearch2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}