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

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

• • 主要知识点
  • 习题
  • • 1. Leetcode 414. 第三大的数
    • • 题目描述
      • 初见
      • 代码
  • 总结

十大排序算法都会了么？

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
提示： 1 ≤ n u m s . l e n g t h ≤ 104 1 le nums.length le 104 1≤nums.length≤104
− 231 ≤ n u m s [ i ] ≤ 231 − 1 -231 le nums[i] le 231 - 1 −231≤nums[i]≤231−1

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

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

解法1：遍历法

class Solution {
public:
    int thirdMax(vector& 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& 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& 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. 排序算法很重要