find second and third maximum element array java

Question

I have to find 1st, 2nd, and 3rd largest array. I know I could simply sort it and return array[0], array[1], array[3]. But the problem is, i need the index, not the value. For example if i have float[] listx={8.0, 3.0, 4.0, 5.0, 9.0} it should return 4, 0, and 3.

Here's the code I have but it doesn't work:

//declaration max1-3        
public void maxar (float[] listx){

    float maxel1=0;
    float maxel2=0;
    float maxel3=0;

    for (int i=0; i<listx.length; i++){
        if(maxel1<listx[i])
        {maxel1=listx[i];
        max1=i;
        }
    }
    listx[max1]=0; //to exclude this one in nextsearch

    for (int j=0; j<listx.length; j++){
        if(listx[j]>maxel2)
        {maxel2=listx[j];
        max2=j;
        }
    }
    listx[max2]=0;

    for (int k=0; k<listx.length; k++){
        if(listx[k]>maxel3)
        {maxel3=listx[k];
        max3=k;
        }
    }
}

I get max1 right but after that all the elements turns to 0. hence max2 and max3 become 0. Please suggest me what is wrong with this solution. Thank you.

Check [this](http://stackoverflow.com/questions/2615712/finding-the-second-highest-number-in-array) post — Extreme Coders, Dec 01 '12 at 18:49

score 2 · Answer 1 · answered Dec 01 '12 at 18:50

You can find the three elements using a single loop, and you don't need to modify the array.

When you come across a new largest element, you need to shift the previous largest and the previous second-largest down by one position.

Similarly, when you find a new second-largest element, you need to shift maxel2 into maxel3.

Instead of using the three variables, you might want to employ an array. This will enable you to streamline the logic, and make it easy to generalize to k largest elements.

score 0 · Answer 2 · answered Dec 01 '12 at 18:42

0

Make 3 passes over array: on first pass find value and 1st index of maximum element M1, on second pass find value and 1st index of maximum element M2 which is lesser than M1 and on third pass find value/1st index M3 < M2.

answered Dec 01 '12 at 18:42

Victor Sorokin

11,878
2
35
51

2

3 passes is overkill. Only one pass is necessary. – Victor Zamanian Dec 01 '12 at 18:45

score 0 · Answer 3 · answered Dec 01 '12 at 18:53

Try this code it will work :)

  public class Array
    {
  public void getMax( double ar[] )
   {
    double max1 = ar[0]; // Assume the first
    double max2 = ar[0]; // element in the array
    double max3 = ar[0]; // is the maximum element.
    int ZERO = 0; 
     // Variable to store inside it the index of the max value to set it to zero.

    for( int i = 0; i < ar.length; i++ )
    {
        if( ar[i] >= max1)
        {
            max1 = ar[i];
            ZERO = i;
        }
    }

    ar[ZERO] = 0; // Set the index contains the 1st max to ZERO.

    for( int j = 0; j < ar.length; j++ )
    {
        if( ar[j] >= max2 )
        {
            max2 = ar[j];
            ZERO = j;
        }
    }

    ar[ZERO] = 0; // Set the index contains the 2st max to ZERO.

    for( int k = 0; k < ar.length; k++ )
    {
        if( ar[k] >= max3 )
        {
            max3 = ar[k];
            ZERO = k;
        }
    }

            System.out.println("1st max:" + max1 + ", 2nd: " +max2 + ",3rd: "+ max3);                              
   }

public static void main(String[] args)
{
    // Creating an object from the class Array to be able to use its methods.
    Array array = new Array();
    // Creating an array of type double.
    double a[] = {2.2, 3.4, 5.5, 5.5, 6.6, 5.6};

    array.getMax( a ); // Calling the method that'll find the 1st max, 2nd max, and      and 3rd max.
}

  }

score 0 · Answer 4 · answered Dec 01 '12 at 21:10

I suggest making a single pass instead of three for optimization. The code below works for me. Note that the code does not assert that listx has at least 3 elements. It is up to you to decide what should happen in case it contains only 2 elements or less.

What I like about this code is that it only does one pass over the array, which in its best case would have faster running time compared to doing three passes, with a factor proportionate to the number of elements in listx.

Assume i1, i2 and i3 store the indices of the three greatest elements in listx, and i0 is one of i1, i2 and i3 that points to the smallest element. In the beginning, i1 = i2 = i3 because we haven't found the largest elements yet. So let i0 = i1. If we find a new index j such that that listx[j] > listx[i0], we set i0 = j, replacing that old index with an index that leads to a greater element. Then we find the index among i1, i2 and i3 that now leads to the smallest element of out the three, so that we can safely discard that one in case a new large element comes along.

Note: This code is in C, so translate it to Java if you want to use it. I made sure to use similar syntax to make that easier. (I wrote it in C because I lacked a Java testing environment.)

void maxar(float listx[], int count) {
    int maxidx[3] = {0};

    /* The index of the 3rd greatest element
     * in listx.
     */
    int max_3rd = 0;

    for (int i = 0; i < count; i++) {
        if (listx[maxidx[max_3rd]] < listx[i]) {
            /* Exchange 3rd greatest element
             * with new greater element.
             */
            maxidx[max_3rd] = i;

            /* Find index of smallest maximum. */
            for (int j = (max_3rd + 1) % 3; j != max_3rd; j = (j + 1) % 3) {
                if (listx[maxidx[j]] < listx[maxidx[max_3rd]]) {
                    max_3rd = j;
                }
            }
        }
    }

    /* `maxidx' now contains the indices of
     * the 3 greatest values in `listx'.
     */

    printf("3 maximum elements (unordered):\n");
    for (int i = 0; i < 3; i++) {
        printf("index: %2d, element: %f\n", maxidx[i], listx[maxidx[i]]);
    }
}

score 0 · Answer 5 · answered Aug 27 '14 at 05:28

public class ArrayExample {
    public static void main(String[] args) {
        int secondlargest = 0;
        int thirdLargest=0;
        int largest = 0;
        int arr[] = {5,4,3,8,12,95,14,376,37,2,73};
        for (int i = 0; i < arr.length; i++) {
            if (largest < arr[i]) {
                secondlargest = largest;
                largest = arr[i];
            }
            if (secondlargest < arr[i] && largest != arr[i])
                secondlargest = arr[i];
            if(thirdLargest<arr[i] && secondlargest!=arr[i] && largest!=arr[i] && thirdLargest<largest && thirdLargest<secondlargest)
                thirdLargest =arr[i];
        }
        System.out.println("Largest number is: " + largest);
        System.out.println("Second Largest number is: " + secondlargest);
        System.out.println("third Largest number is: " + thirdLargest);
    }
}

score 0 · Answer 6 · edited Dec 05 '15 at 17:03

0

def third_mar_array(arr):
    max1=0
    max2=0
    max3=0
    for i in range(0,len(arr)-1):
         if max1<arr[i]:
             max1=arr[i]
             max_in1=i
    arr[max_in1]=0
    for j in range(0,len(arr)-1):
         if max2<arr[j]:
             max2=arr[j]
             max_in2=j
    arr[max_in2]=0
    for k in range(0,len(arr)-1):
         if max3<arr[k]:
             max3=arr[k]
             max_in3=k
    #arr[max_in3]=0
    return max3

n=[5,6,7,3,2,1]

f=first_array(n)
print f

edited Dec 05 '15 at 17:03

Bhargav Rao

50,140
28
121
140

answered Dec 05 '15 at 16:55

Harsh jain

1

Please, add a description of the solution you are proposing. – il_raffa Dec 05 '15 at 17:13

score 0 · Answer 7 · edited Jul 02 '21 at 09:12

import java.util.Scanner;

class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testcase = sc.nextInt();

        while (testcase-- > 0) {
            int sizeOfArray = sc.nextInt();
            int[] arr = new int[sizeOfArray];
            for (int i = 0; i < sizeOfArray; i++) {
                arr[i] = sc.nextInt();
            }

            int max1, max2, max3;
            max1 = 0;
            max2 = 0;
            max3 = 0;

            for (int i = 0; i < sizeOfArray; i++) {
                if (arr[i] > max1) {
                    max3 = max2;
                    max2 = max1;
                    max1 = arr[i];
                }
                else if (arr[i] > max2) {
                    max3 = max2;
                    max2 = arr[i];
                }
                else if (arr[i] > max3) {
                    max3 = arr[i];
                }
            }

            System.out.println(max1 + " " + max2 + " " + max3);
        }
    }
}

find second and third maximum element array java

7 Answers7