# 一系列不同元素中的第三大元素 > 原文： [https://www.geeksforgeeks.org/third-largest-element-array-distinct-elements/](https://www.geeksforgeeks.org/third-largest-element-array-distinct-elements/) 給定 n 個整數數組，找到第三大元素。 數組中的所有元素都是不同的整數。 **示例**： ``` Input: arr[] = {1, 14, 2, 16, 10, 20} Output: The third Largest element is 14 Explanation: Largest element is 20, second largest element is 16 and third largest element is 14 Input: arr[] = {19, -10, 20, 14, 2, 16, 10} Output: The third Largest element is 16 Explanation: Largest element is 20, second largest element is 19 and third largest element is 16 ``` **樸素的方法** ：任務是首先找到最大的元素，然后找到第二大的元素，然后將它們都排除，找到第三大的元素。 基本思想是對數組進行兩次迭代，標記最大和第二最大元素，然后將它們排除在外，同時找到第三最大元素，即不包括最大和第二最大的最大元素。 * **算法**： 1. 首先，遍歷數組并找到最大值。 2. 將其與索引一起存儲為第一個最大值。 3. 現在遍歷整個數組，找到第二個最大值，不包括最大值元素。 4. 最后第三次遍歷數組，找到第三大元素，即不包括最大值和第二最大值。 * ## C++ ``` // C++ program to find third Largest // element in an array of distinct elements #include <bits/stdc++.h> void thirdLargest(int arr[], int arr_size) { ????/* There should be atleast three elements */ ????if (arr_size < 3) ????{ ????????printf(" Invalid Input "); ????????return; ????} ????// Find first largest element ????int first = arr[0]; ????for (int i = 1; i < arr_size ; i++) ????????if (arr[i] > first) ????????????first = arr[i]; ????// Find second largest element ????int second = INT_MIN; ????for (int i = 0; i < arr_size ; i++) ????????if (arr[i] > second && arr[i] < first) ????????????second = arr[i]; ????// Find third largest element ????int third = INT_MIN; ????for (int i = 0; i < arr_size ; i++) ????????if (arr[i] > third && arr[i] < second) ????????????third = arr[i]; ????printf("The third Largest element is %d\n", third); } /* Driver program to test above function */ int main() { ????int arr[] = {12, 13, 1, 10, 34, 16}; ????int n = sizeof(arr)/sizeof(arr[0]); ????thirdLargest(arr, n); ????return 0; } ``` ## Java ``` // Java program to find third? // Largest element in an array // of distinct elements class GFG { static void thirdLargest(int arr[], ?????????????????????????int arr_size) { ????/* There should be? ????atleast three elements */ ????if (arr_size < 3) ????{ ????????System.out.printf(" Invalid Input "); ????????return; ????} ????// Find first? ????// largest element ????int first = arr[0]; ????for (int i = 1; ?????????????i < arr_size ; i++) ????????if (arr[i] > first) ????????????first = arr[i]; ????// Find second? ????// largest element ????int second = Integer.MIN_VALUE; ????for (int i = 0;? ?????????????i < arr_size ; i++) ????????if (arr[i] > second &&? ????????????arr[i] < first) ????????????second = arr[i]; ????// Find third ????// largest element ????int third = Integer.MIN_VALUE; ????for (int i = 0;? ?????????????i < arr_size ; i++) ????????if (arr[i] > third &&? ????????????arr[i] < second) ????????????third = arr[i]; ????System.out.printf("The third Largest " +? ??????????????????"element is %d\n", third); } // Driver code public static void main(String []args) { ????int arr[] = {12, 13, 1,? ?????????????????10, 34, 16}; ????int n = arr.length; ????thirdLargest(arr, n); } } // This code is contributed // by Smitha ``` ## Python3 ``` # Python 3 program to find? # third Largest element in? # an array of distinct elements import sys def thirdLargest(arr, arr_size): ????# There should be? ????# atleast three elements? ????if (arr_size < 3): ????????print(" Invalid Input ") ????????return ????# Find first? ????# largest element ????first = arr[0] ????for i in range(1, arr_size): ????????if (arr[i] > first): ????????????first = arr[i] ????# Find second ????# largest element ????second = -sys.maxsize ????for i in range(0, arr_size): ????????if (arr[i] > second and? ????????????arr[i] < first): ????????????second = arr[i] ????# Find third? ????# largest element ????third = -sys.maxsize ????for i in range(0, arr_size): ????????if (arr[i] > third and ????????????arr[i] < second): ????????????third = arr[i] ????print("The Third Largest",? ??????????"element is", third) # Driver Code arr = [12, 13, 1,? ???????10, 34, 16] n = len(arr) thirdLargest(arr, n) # This code is contributed? # by Smitha ``` ## C# ``` // C# program to find third? // Largest element in an array? // of distinct elements using System; class GFG { static void thirdLargest(int []arr, ?????????????????????????int arr_size) { ????/* There should be? ????atleast three elements */ ????if (arr_size < 3) ????{ ????????Console.Write(" Invalid Input "); ????????return; ????} ????// Find first? ????// largest element ????int first = arr[0]; ????for (int i = 1; ?????????????i < arr_size ; i++) ????????if (arr[i] > first) ????????????first = arr[i]; ????// Find second ????// largest element ????int second = -int.MaxValue; ????for (int i = 0;? ?????????????i < arr_size ; i++) ????????if (arr[i] > second &&? ????????????arr[i] < first) ????????????second = arr[i]; ????// Find third? ????// largest element ????int third = -int.MaxValue; ????for (int i = 0; ?????????????i < arr_size ; i++) ????????if (arr[i] > third &&? ????????????arr[i] < second) ????????????third = arr[i]; ????Console.Write("The third Largest " +? ??????????????????"element is "+ third); } // Driver code public static void Main() { ????int []arr = {12, 13, 1,????? ?????????????????10, 34, 16}; ????int n = arr.Length; ????thirdLargest(arr, n); } } // This code is contributed by Smitha ``` ## PHP ``` <?php // PHP program to find third? // Largest element in an array // of distinct elements function thirdLargest($arr, $arr_size) { ????/* There should be atleast ????three elements */ ????if ($arr_size < 3) ????{ ????????echo " Invalid Input "; ????????return; ????} ????// Find first largest element ????$first = $arr[0]; ????for ($i = 1; $i < $arr_size ; $i++) ????????if ($arr[$i] > $first) ????????????$first = $arr[$i]; ????// Find second largest element ????$second = PHP_INT_MIN; ????for ($i = 0; $i < $arr_size ; $i++) ????????if ($arr[$i] > $second &&? ???????????????$arr[$i] < $first) ????????????$second = $arr[$i]; ????// Find third largest element ????$third = PHP_INT_MIN; ????for ($i = 0; $i < $arr_size ; $i++) ????????if ($arr[$i] > $third &&? ??????????????$arr[$i] < $second) ????????????$third = $arr[$i]; ????echo "The third Largest element is ",? ?????????????????????????????$third,"\n"; } // Driver Code $arr = array(12, 13, 1,? ?????????????10, 34, 16); $n = sizeof($arr); thirdLargest($arr, $n); // This code is contributed by m_kit ?> ``` * **輸出**： ``` The third Largest element is 13 ``` * **復雜度分析**： * **時間復雜度**：`O(n)`。 由于數組要重復三次并在固定時間內完成 * **空間復雜度**：`O(1)`。 不需要多余的空間，因為索引可以存儲在恒定空間中。 **有效方法**：該問題涉及在單個遍歷中查找數組中的第三大元素。 可以借助類似的問題-[找到第二個最大元素](https://www.geeksforgeeks.org/find-second-largest-element-array/)來破解該問題。 因此，想法是從頭到尾遍歷數組，并跟蹤直到該索引*（存儲在變量中）*的三個最大元素。 因此，遍歷整個數組后，變量將存儲數組的三個最大元素的索引*（或值）*。 * **算法**： 1. 創建三個變量，*第一個*，*第二個*，*第三個*，以存儲數組中三個最大元素的索引。 （最初將它們全部初始化為最小值）。 2. 沿著輸入數組從頭到尾移動。 3. 對于每個索引，請先檢查元素是否大于*，然后再大于*。 如果元素較大，則首先更新*的值，如果元素較大，則將*的值首先分配給*，然后將*分配給第二位，將*分配給*。 第三*。 因此，最大的元素將被更新，以前存儲為最大的元素將成為第二大元素，第二大的元素將成為第三大元素。* 4. 否則，如果元素大于 *second* ，則更新 *second* 的值，第二大元素變為第三大元素。 5. 如果前兩個條件失敗，但是元素大于*第三*，則更新*第三*。 6. 從頭到尾遍歷數組后，打印*值的第三個* * ## C++ ```cpp // C++ program to find third? // Largest element in an array #include <bits/stdc++.h> void thirdLargest(int arr[], int arr_size) { ????/* There should be atleast three elements */ ????if (arr_size < 3) ????{ ????????printf(" Invalid Input "); ????????return; ????} ????// Initialize first, second and third Largest element ????int first = arr[0], second = INT_MIN, third = INT_MIN; ????// Traverse array elements to find the third Largest ????for (int i = 1; i < arr_size ; i ++) ????{ ????????/* If current element is greater than first, ???????????then update first, second and third */ ????????if (arr[i] > first) ????????{ ????????????third? = second; ????????????second = first; ????????????first? = arr[i]; ????????} ????????/* If arr[i] is in between first and second */ ????????else if (arr[i] > second) ????????{ ????????????third = second; ????????????second = arr[i]; ????????} ????????/* If arr[i] is in between second and third */ ????????else if (arr[i] > third) ????????????third = arr[i]; ????} ????printf("The third Largest element is %d\n", third); } /* Driver program to test above function */ int main() { ????int arr[] = {12, 13, 1, 10, 34, 16}; ????int n = sizeof(arr)/sizeof(arr[0]); ????thirdLargest(arr, n); ????return 0; } ```