Preface explains

Algorithm learning, daily brush record.

Subject to connect

The third largest number

The subject content

Given a non-empty array, return the third largest number in the array. If not, return the largest number in the array.

Example 1:

Input: [3, 2, 1]

Output: 1.

Explanation: The third largest number is 1.

Example 2:

Input: [1, 2]

Output: 2

Explanation: The third largest number does not exist, so return the largest number 2.

Example 3:

Input: [2, 2, 3, 1]

Output: 1.

Note that the third largest number is the number that is the third largest among all the different numbers.

There are two numbers with a value of 2 in this example, and they are both second. The third largest number of all the different numbers is 1.

Tip:

1 <= nums.length <= 10^4

-2^31 <= nums[i] <= 2^31 – 1

The analysis process

Find the largest number, the second largest number, and finally the third largest number through three iterations.

The first time through, the traditional comparison method, find the largest number.

The second iteration, following the traditional method of comparison, finds the second largest number, but the judgment condition is added to the number less than the first.

The third iteration, following the traditional method of comparison, finds the third largest number, but the judgment condition is to add less than the second largest number.

Finally, if the third largest number is found, return the third largest number; If no third largest number is found, the first largest number is returned.

The time complexity is O(3n), the constant term can be removed, O(3n)=O(n), so the time complexity is O(n).

To solve the code

Class Solution {public int thirdMax(int[] nums) {public int thirdMax(int[] nums) {public int thirdMax(int[] nums) { O(3n)=O(n) // define the first large number int first = -2147483648; For (int num: nums) {if (num >= first) {first = num; } // define the second largest number int second = -2147483648; For (int num: nums) {if (num >= second &&num < first) {second = num; } // define the third largest number int third = -2147483648; Boolean isFind = false; For (int num: nums) {if (num >= third && num < second) {third = num; isFind = true; }} if (isFind) {return third; } else {// If the third largest number is not found, return first; }}}Copy the code

Submit the results

It took 1ms to execute, beating 95.10% of users in time, 38.2MB in memory consumption, and 73.55% in space.

The original link

The third largest number