百度怎样注册免费的网站,个人做跨境电商网站有哪些,庭院景观设计,域名访问wordpress目录
重点整理
054、 拼数
题目描述
输入格式
输出格式
输入输出样例
核心思路
代码
055、 求第k小的数
题目描述
输入格式
输出格式
输入输出样例
核心思路
代码
总结 这几天我们主要刷了洛谷上排序算法对应的一些题目#xff0c;相对来说比较简单 一共是13道…目录
重点整理
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复制对于
7424613
核心思路
本质来看还是一个自定义排序规则但是这个题巧妙之处就是自定义的排序规则是如何确定的。对于两个字符串如果将比较规则定义为大的放前面那对于 32132这个例子来说的话大的放前面那就是32132但是32321要更大。所以简单的大的放前面是不合适的。
如果我们把比较规则定义为 ab大于ba那么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 ComparatorString() {public int compare(String o1, String o2) {return (o2o1).compareTo(o1o2);}});for (int i 0; i n; i) {System.out.print(s[i]);}}
}
055、 求第k小的数
题目描述
输入 nn1≤n50000001≤n5000000 且 nn 为奇数个数字 aiai1≤ai1091≤ai109输出这些数字的第 kk 小的数。最小的数是第 00 小。
请尽量不要使用 nth_element 来写本题因为本题的重点在于练习分治算法。
输入格式
无
输出格式
无
输入输出样例
输入 #1复制
5 1
4 3 2 1 5输出 #1复制
2
核心思路
这个题看起来并没有什么难度但是题目给的样例卡时间最后两个数据量太大经典的快排和归并都会超时间。
我们回顾一下快排的思路确定枢轴的过程是实质上就是把这个元素放到其排序后的正确位置上去其实就是把第k小的数放在下标为k的位置上根据这个思路我们可以在快排的代码上做优化。 我们在快排的基础上确定好枢轴位置后判断该位置是否是k是的话直接结束程序不是的话继续往后为了节约时间我们只排序k所在的那个区间。 代码
#include iostream
#include vector
using namespace std; const int N5e6 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;
}
总结
排序还是非常博大精深的希望在后续的学习中不断精进
