20240627 寻找数组中第二大的数

题目：求数组中第二大的数

我的思路

• 一个一个去比较
• 遍历一遍

两个变量

如果数组的长度大于2，

就分别放进max，smax中，

放进去开始一个一个往后看

m[i]先和max比较，m[i]最大进行处理

如果m[i]不是最大，则smax进行比较和处理

反正被吐槽说思路古朴了

思路二：

• 遍历两遍，第一遍找最大值，第二遍找第二大值

#include <iostream>
#include <vector>
#include <climits> // For INT_MIN

int getSecondMaxNum(const std::vector<int>& arr) {
    int max = INT_MIN, secondMax = INT_MIN;

    for (int i = 0; i < arr.size(); ++i) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }

    for (int j = 0; j < arr.size(); ++j) {
        if (arr[j] < max && arr[j] > secondMax) {
            secondMax = arr[j];
        }
    }

    return secondMax;
}

int main() {
    std::vector<int> arr = {1, 2, 8, 5};
    std::cout << "Second Max Number: " << getSecondMaxNum(arr) << std::endl;
    return 0;
}

思路三：部分快速排序，再取第二个

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int partition(vector<int>& nums, int low, int high)
{
    int pivot = nums[high];//提取基准
    int i = low - 1;
    
    for (int j = low; j < high; ++j) 
    {
        if (nums[j] > pivot)
        {
            ++i;//为什么i要写在这个地方我真的不理解
            swap(nums[i], nums[j]);
        }
    }
    swap(nums[i + 1], nums[high]);//基准点到它该去的地方
    return i + 1;
}

//写代码不一定要那么具体到一个数据一个数据到位，我们抽象一点，再具体实现
int findKthLargest(vector<int>& nums, int k, int low, int high) 
{
    if (low <= high) 
    {
        int pi = partition(nums, low, high);//全范围找基准点定位
        if (pi == k - 1) 
        {
            return nums[pi];
        } 
        else if (pi > k - 1) 
        {
            return findKthLargest(nums, k, low, pi - 1);//后半部分找基准点定位
        } 
        else 
        {
            return findKthLargest(nums, k, pi + 1, high);//前半部分找基准点定位
        }
    }
    return -1;
}

int findSecondLargest(vector<int>& nums)
{
    int n = nums.size();
    return findKthLargest(nums, 2, 0, n - 1);
}

int main() {
    vector<int> nums = {3, 2, 1, 5, 6, 4};
    int secondLargest = findSecondLargest(nums);
    cout << "The second largest number is: " << secondLargest << endl;
    return 0;
}

思路四:部分冒泡排序，排两次就可以了