《C语言入门100例》(第13例)给定三个数 a，b，c，从小到大输出这三个数 | 最原始的排序算法思想

【第13题】给定三个数 a，b，c，从小到大输出这三个数 | 最原始的排序算法思想

主要知识点

十大排序算法都会了么？

习题

1. Leetcode 414. 第三大的数

题目描述

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
提示：$1\le nums.length\le 104$
$-231\le nums[i]\le 231-1$

初见

解法1：遍历法
  由于需要寻找第三大的数，因此可以将前三大的数均记录下来，并根据新数进行更新。由于相同的数不算在内，因此这里要注意更新条件。

解法2：排序法
  排序后对排序结果进行查找，跳过相同元素的数，直至找到第三大的数。

代码

解法1：遍历法

class Solution {
public:
int thirdMax(vector<int>& nums) {
long long max(LONG_MIN), mmax(LONG_MIN), mmmax(LONG_MIN); // 大->小
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] > mmmax) { // 比第三大的数大，更新
if (nums[i] > mmax) { // 比第二大的数大
if (nums[i] > max) {
mmmax = mmax;
mmax = max;
max = nums[i];
} else if (nums[i] == max){ // 注意相等时不更新
;
} else {
mmmax = mmax;
mmax = nums[i];
}
} else if (nums[i] == mmax) { // 注意相等时不更新
;
} else {
mmmax = nums[i];
}
} else {
;
}
}
if (mmmax > LONG_MIN) {
return mmmax;
} else {
return max;
}
}
};

解法2：排序法

class Solution {
public:
void qSort(vector<int>& nums, int low, int high) { // 快速排序
if (low >= high) {
return;
}
int pivot = nums[low];
int l(low), r(high);
while (l < r) {
while (nums[r] > pivot) {
r--;
}
if (l < r) {
nums[l] = nums[r];
}
while (nums[l] <= pivot && l < r) {
l++;
}
if (l < r) {
nums[r] = nums[l];
}
}
nums[l] = pivot;
qSort(nums, low, l - 1);
qSort(nums, l + 1, high);
}
int thirdMax(vector<int>& nums) {
int resIdx(0);
qSort(nums, 0, nums.size() - 1);
for (int i = nums.size() - 1, diff = 1; i > 0; i--) { // 对排序后的数组进行查找
if (nums[i] != nums[i - 1]) {
diff++;
// std::cout << nums[i]
<< " " << diff << std::endl;
if (diff == 3) {
nums[nums.size() - 1] = nums[i - 1];
}
}
}
return nums[nums.size() - 1];
}
};

总结

1. 排序算法很重要

最后

以上就是坚强母鸡为你收集整理的《C语言入门100例》(第13例)给定三个数 a，b，c，从小到大输出这三个数 | 最原始的排序算法思想的全部内容，希望文章能够帮你解决《C语言入门100例》(第13例)给定三个数 a，b，c，从小到大输出这三个数 | 最原始的排序算法思想所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。