Find Three Largest Numbers


Find Three Largest Numbers [Easy]

  • Write a function that takes in an array of at least three integers and, without sorting the input array, returns a sorted array of the three largest integers in the input array.
  • The function should return duplicate integers if necessary; for example, it should return [10, 10, 12] for an input array of [10, 5, 9, 10, 12].

**Sample Input **

array = [141, 1, 17, -7, -17, -27, 18, 541, 8, 7, 7]

**Sample Output **

[18, 141, 541]


Hints

Hint 1
Can you keep track of the three largest numbers in an array as you traverse the input array?


Hint 2
Following the suggestion in Hint #1, try traversing the input array and updating the three largest numbers if necessary by shifting them accordingly.


Method 1

【O(n)time∣O(1)space】
package Searching;

import java.util.Arrays;

/**
 * @author zhengstars
 * @date 2023/06/07
 */
public class FindThreeLargestNumbers {
    public static int[] findThreeLargestNumbers(int[] array) {
        // Create an array to store the three largest numbers
        int[] largestNums = {Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE};

        // Iterate over the input array
        for (int i = 0; i < array.length; i++) {
            // Compare the current element with the largest numbers

            // If the current element is greater than the third largest number,
            // shift the values and update the third largest number
            if (array[i] > largestNums[2]) {
                largestNums[0] = largestNums[1];
                largestNums[1] = largestNums[2];
                largestNums[2] = array[i];
            }
            // If the current element is greater than the second largest number,
            // shift the values and update the second largest number
            else if (array[i] > largestNums[1]) {
                largestNums[0] = largestNums[1];
                largestNums[1] = array[i];
            }
            // If the current element is greater than the first largest number,
            // update the first largest number
            else if (array[i] > largestNums[0]) {
                largestNums[0] = array[i];
            }
        }

        // Return the array containing the three largest numbers
        return largestNums;
    }


    public static void main(String[] args) {
        int[] array = {141, 1, 17, -7, -17, -27, 18, 541, 8, 7, 7};
        int[] result = findThreeLargestNumbers(array);
        System.out.println(Arrays.toString(result));
    }
}




Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • 2379. Minimum Recolors to Get K Consecutive Black Blocks
  • 2471. Minimum Number of Operations to Sort a Binary Tree by Level
  • 1387. Sort Integers by The Power Value
  • 2090. K Radius Subarray Averages
  • 2545. Sort the Students by Their Kth Score