C ++程序查找具有不同元素的数组中的第三个最大元素

给定一个n个整数的数组，找到第三个最大的元素。数组中的所有元素都是不同的整数。

示例：

输入: arr [] = {1,14,2,16,10,20}
输出: 第三个最大的元素是14

解释: 最大的元素是20，第二大的元素是16，第三大的元素是14

输入: arr[] = {19,-10,20,14,2,16,10}
输出: 第三个最大的元素是16

解释: 最大的元素是20，第二大的元素是19，第三大的元素是16

朴素方法： 首先找到最大元素，其次是第二大元素，然后排除它们两个找到第三个最大元素。基本思想是遍历数组两次，标记最大和第二大元素，然后排除它们两个找到第三个最大元素，即排除了最大和第二大元素的最大元素。

算法：
1. 首先，遍历整个数组并找到最大值。
2. 将其作为第一个最大值与其索引一起存储。
3. 现在遍历整个数组，找到第二个最大值，不包括最大元素。
4. 最后第三次遍历数组并找到第三个最大元素，即排除最大和第二大元素。

// C ++程序在具有不同元素的数组中查找第三个最大元素
// include <bits/stdc++.h>
  
void thirdLargest(int arr [], int arr_size)
{
/ *数组中应至少有三个元素* /
if (arr_size <3)
{
printf("无效输入");
返回;
}
  
//找到第一个最大元素
int first = arr [0];
for（int i = 1; i <arr_size; i ++）
如果（arr [i] > first）
first = arr [i];

//找到第二大的元素
int second = INT_MIN;
for（int i = 0; i <arr_size; i ++）
如果（arr [i] > second && arr [i] <first）
second = arr [i];

//找到第三个最大元素
int third = INT_MIN;
for（int i = 0; i <arr_size; i ++）
如果（arr [i] > third && arr [i] <second）
third = arr [i];

printf("第三个最大的元素是%d
", third);
}
  
/*主程序测试上述函数*/
int main()
{
int arr [] = {12，13，1，10，34，16};
int n = sizeof(arr) / sizeof(arr [0]);
thirdLargest（arr，n）;
返回0;
}

输出：

第三个最大的元素是13

复杂度分析：
- 时间复杂度： O（n）。数组被迭代三次，并且在常数时间内完成。
- 空间复杂度：不需要额外的空间，因为索引可以存储在常量空间中。

有效方法： 该问题涉及在单个遍历中查找数组中的第三个最大元素。可以通过利用类似问题的帮助来解决该问题——查找第二个最大元素。所以想法是从开始到结束遍历数组并跟踪到该索引为止的三个最大元素(存储在变量中)。因此，在遍历整个数组之后，变量将存储数组的三个最大元素的索引(或值)。

算法:
1. 创建三个变量 first 、 second 和 third ，用于存储数组的三个最大元素的索引。(最初它们都初始化为最小值)。
2. 从开头到结束沿着输入数组移动。
3. 对于每个索引，检查元素是否大于 first 。如果元素较大，则更新 first 的值。如果元素较大，请将 first 的值分配给 second ，将 second 的值分配给 third 。因此，最大的元素被更新，之前存储为最大的元素成为第二大，第二大的元素成为第三大。
4. 否则，如果元素比 second 大，则可以更新 second 的值，第二大的元素成为第三大。
5. 如果前两个条件失败，但元素大于 third ，则更新 third 。
6. 遍历数组从开始到结束，打印 third 的值

//C ++程序以查找数组中的第三个最大元素
#include <bits/stdc++.h>
  
void thirdLargest(int arr[], int arr_size)
{
    /* 数组中至少应该有三个元素 */
    if (arr_size < 3)
    {
        printf(" Invalid Input ");
        return;
    }
  
    // 初始化第一个、第二个和第三个最大元素
    int first = arr[0], second = INT_MIN, third = INT_MIN;
  
    // 遍历数组元素以查找第三个最大元素
    for (int i = 1; i < arr_size ; i ++)
    {
        /* 如果当前元素大于第一个，那么更新第一个、第二个和第三个元素*/
        if (arr[i] > first)
        {
            third  = second;
            second = first;
            first  = arr[i];
        }
  
        /* 如果arr[i]介于第一个和第二个之间 */
        else if (arr[i] > second)
        {
            third = second;
            second = arr[i];
        }
  
        /* 如果arr[i]介于第二个和第三个之间 */
        else if (arr[i] > third)
            third = arr[i];
    }
  
    printf("第三个最大元素是%d\n", third);
}
  
/* 主程序测试以上函数 */
int main()
{
    int arr[] = {12, 13, 1, 10, 34, 16};
    int n = sizeof(arr)/sizeof(arr[0]);
    thirdLargest(arr, n);
    return 0;
}