暑假算法刷题日记 Day 10

重点整理

054、拼数

题目描述

输入格式

输出格式

输入输出样例

核心思路

代码

055、求第k小的数

题目描述

输入格式

输出格式

输入输出样例

核心思路

代码

总结

这几天我们主要刷了洛谷上排序算法对应的一些题目，相对来说比较简单

一共是13道题，对应我暑假刷题的043--055。当然这些题目相对来说比较简单，我们挑着重点的说。

重点整理

排序这一块的题目总体来看包括，

1. 基本的排序算法，像快速排序、分治排序，这些知识点我写了专门的博客，欢迎大家阅读

快速排序、归并排序

2. 结构题的多因素、自定义排序规则。Java实现自定义排序

3. 特殊问题

针对这个特殊问题，我们就题目来说

054、拼数

题目描述

设有 nn 个正整数 a1…ana1…an，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。

输入格式

第一行有一个整数，表示数字个数 nn。

第二行有 nn 个整数，表示给出的 nn 个整数 aiai。

输出格式

一个正整数，表示最大的整数

输入输出样例

输入 #1复制

3
13 312 343

输出 #1复制

34331213

输入 #2复制

4
7 13 4 246

输出 #2复制对于

核心思路

本质来看还是一个自定义排序规则，但是这个题巧妙之处就是自定义的排序规则是如何确定的。对于两个字符串，如果将比较规则定义为大的放前面，那对于 321，32，这个例子来说的话，大的放前面那就是32132，但是32321要更大。所以简单的大的放前面是不合适的。

如果我们把比较规则定义为 a+b大于b+a，那么a在前面，反之b在前面。这样就避免了这个问题。

代码

import java.util.*;


public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s[] = new String[n];
        for (int i = 0; i < n; i++) {
            s[i] = sc.next();
        }
        Arrays.sort(s,new Comparator<String>() {
            public int compare(String o1, String o2) {
                return (o2+o1).compareTo(o1+o2);
            }
        });
        for (int i = 0; i < n; i++) {
            System.out.print(s[i]);
        }
    }
}

055、求第k小的数

题目描述

输入 nn（1≤n<50000001≤n<5000000 且 nn 为奇数）个数字 aiai（1≤ai<1091≤ai<109），输出这些数字的第 kk 小的数。最小的数是第 00 小。

请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。

输入格式

无

输出格式

无

输入输出样例

输入 #1复制

5 1
4 3 2 1 5

输出 #1复制

核心思路

这个题看起来并没有什么难度，但是题目给的样例卡时间，最后两个数据量太大，经典的快排和归并都会超时间。

我们回顾一下快排的思路，确定枢轴的过程是实质上就是把这个元素放到其排序后的正确位置上去，其实就是把第k小的数放在下标为k的位置上，根据这个思路我们可以在快排的代码上做优化。

我们在快排的基础上，确定好枢轴位置后，判断该位置是否是k，是的话直接结束程序，不是的话继续往后，为了节约时间，我们只排序k所在的那个区间。

代码

#include <iostream>  
#include <vector>  
using namespace std;  
  const int N=5e6 +10;
 int nums[N];
void quickSort(int left, int right, int k) {  
    // 判断排序区间长度  
    if (right <= left) {  
        if (right == left && left == k) {  
            cout << nums[k] << endl;  
            exit(0);  
        }  
        return;  
    }  
  
    // 选择基准值（这里使用最左边的值）  
    int pivot = nums[left];  
    int i = left, j = right;  
    while (i < j) {  
        // 从右向左找到第一个小于等于pivot的元素  
        while (nums[j] >= pivot && i < j) j--;  
        // 交换  
        if (i < j) nums[i++] = nums[j];  
  
        // 从左向右找到第一个大于pivot的元素  
        while (nums[i] <= pivot && i < j) i++;  
        if (i < j) nums[j--] = nums[i];  
    }  
    nums[i] = pivot;  
  
    // 判断基准值是否为目标位置  
    if (i == k) {  
        cout << nums[k] << endl;  
        exit(0);  
    }  
  
    // 递归排序  
    if (k < i) quickSort(left, i - 1, k);  
    if (k > i) quickSort(i + 1, right, k);  
}  
  
int main() {  
    int n, k;  
    cin >> n >> k;  
    
    for (int i = 0; i < n; i++) {  
        scanf("%d",&nums[i]);  
    }  
  
    
    
    quickSort( 0, n - 1, k); 
  
    return 0;  
}