August 31, 2010
Largest Two Elements – Single Loop
Problem
Given an array of positive integers. Find the first and second largest elements in the array. You are not allowed to use more than one loop in your solution.
Solution
The solution is to use a single loop to find the first and second maximum. The current array element is compared to both first and second maximum values calculated so far then updating them accordingly. Please refer to the code below for more details. In the next post we will solve this problem using divide and conquer technique.
Code
Here is the C++ code to do that using a single loop
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
//Includes #include <iostream> //Name space using namespace std; //Main function void main() { //Array int A[10] = {1, 5, 3, 2, 4}; //Array size int n = 5; //Initialize first and second maximum int max1 = -1; int max2 = -1; //Find the first and second maximum for (int i = 0; i < n; i++) { //if the current element is greater //than the first maximum then we //should update it if (A[i] >= max1) { max1 = A[i]; } //Otherwise compare the current element //with the second maximum and update it //similarly else if (A[i] >= max2) { max2 = A[i]; } //Otherwise keep the first and //second maximum intact else { //Nothing } } //Print out cout << "max1 = " << max1 << endl; cout << "max2 = " << max2 << endl; } |
About Author
Mohammed Abualrob
Software Engineer @ Cisco
One Comment
I guess the code above has a bug. A newer version of the code is available in Python here: https://www.8bitavenue.com/2017/03/how-to-find-second-largest-number-in-python/