Найти третье по величине число в массиве java (включая дубликаты)

На этот вопрос уже может быть дан ответ, но моя проблема в том, что если я передаю повторяющиеся или повторяющиеся значения в данном массиве, это дает неправильный результат. Согласно логике, он должен давать правильное значение, но не уверен, что не так в моем коде. ниже мой код

import java.util.Scanner;
import java.util.Arrays;  

class ThirdLargest{

   static int thirdLar(int arr[],int arr_size)
   {
            int i, largest, secondLargest, thirdLargest; 


        thirdLargest = largest = secondLargest = Integer.MIN_VALUE; 
        for (i = 0; i < arr_size ; i ++) 
        { 
            /* If current element is smaller than 
            largest*/
            if (arr[i] > largest) 
            { 
                thirdLargest = secondLargest; 
                secondLargest = largest; 
                largest = arr[i]; 
            } 

            /* If arr[i] is in between largest and 
            secondLargest then update secondLargest */
            else if (arr[i] > secondLargest) 
            { 
                thirdLargest = secondLargest; 
                secondLargest = arr[i]; 
            } 

            else if (arr[i] > thirdLargest) 
                thirdLargest = arr[i]; 
        }  
        return thirdLargest;
    }  

    public static void main(String args[]){

      //Scanner object for capturing the user input
      Scanner scanner = new Scanner(System.in);


      //Stored the entered value in variable

        /*System.out.print("Enter 5 number of elements:");
        int n = scanner.nextInt();*/
        int n = 5;
        int arr[] = new int[n];
        System.out.println("Enter 5 numbers one by one:");
        for(int i = 0; i < n; i++)
        {
            arr[i] = scanner.nextInt();
        }

      //Call thirdLar method to find largest number among given numbers
      int thirdLarNum = thirdLar(arr,n);
      System.out.println("The Third Largest Number is: "+thirdLarNum);
   }
}

ВЫХОД: если я передаю такие значения, как 10 20 40 20 20 правильный вывод должен быть 10, но возвращающий 20

Я думаю, это дает правильный результат, поскольку вы разрешаете дубликаты

suvojit_007 31.10.2018 14:13

Можете уточнить, хотите ли вы включать дубликаты или нет? В заголовке написано «дубликаты включены», но в вашем примере похоже, что вы хотите игнорировать дубликаты.

Illyes Istvan 31.10.2018 14:14

@Illyes Istvan Я имею в виду, что он должен игнорировать дубликаты и должен давать правильный результат

teja 01.11.2018 15:27
1
3
1 663
4
Перейти к ответу Данный вопрос помечен как решенный

Ответы 4

Ответ принят как подходящий

Чтобы убедиться, что largest, secondLargest и thirdLargest уникальны, вам следует добавить дополнительные проверки:

        ...
        else if (arr[i] > secondLargest && arr[i] != largest) 
                                        --------------------
        { 
            thirdLargest = secondLargest; 
            secondLargest = arr[i]; 
        } 

        else if (arr[i] > thirdLargest && arr[i] != largest && arr[i] != secondLargest) 
                                       -----------------------------------------------
            thirdLargest = arr[i]; 
        ...

Идеальный ответ, который требует O (n) и без лишнего места

venu46 16.12.2020 15:10

Вы можете использовать Set вместо массива, чтобы исключить повторяющиеся значения и преобразовать их в массив

Set<int> set = new HashSet<>();

for(int i = 0; i < n; i++)
{
    set.add(scanner.nextInt());
}

int thirdLarNum = thirdLar(set.toArray(), n);

Или используйте set в thirdLar вместо массива

static int thirdLar(Set<int> set)
{
    for (int number : set) {
        if (number  > largest) {
            //...
        }
    }
}

спасибо, но я не хочу импортировать коллекции из-за проблем с памятью в проекте, поэтому я пытаюсь найти, используя только массивы

teja 01.11.2018 15:28

мы можем добиться этого, используя приведенный ниже код.

int[] a = {1,10,33,55};
List<Integer> list=Arrays.asList(a); 
int total = list.size; 
Collections.sort(list);  
int element=list.get(total-3);

потерпит неудачу с 1,10,33,55,55

XtremeBaumer 31.10.2018 14:33

@Ritesh Singh, я думаю, это не рекомендуемая логика, поскольку здесь мы просто берем элемент индекса после сортировки. в этом случае он потерпит неудачу с дубликатами

teja 02.11.2018 07:13

Вы можете использовать Streams:

Я использую здесь IntStream, который не поддерживает сортировку Comparator, что может разрешить Collections.reverseSort (), поэтому я должен отрицать каждый int перед сравнением - и возвращать отрицательное значение;

import java.util.Arrays;

public class Main {

    static int thirdLar(final int[] arr) {

        final int[] array = Arrays.stream(arr).map(i -> -i).sorted().distinct().limit(3).toArray();

        return -array[Math.min(2, array.length - 1)];
    }

    public static void main(final String args[]) {

        System.out.println(thirdLar(new int[] { 1, 5, 2, 5, 10, 2, 2, 5, 10, 12, 25, 1, 5 }));

    }
}

Редактировать: этот код позволяет легко найти n-й по величине

import java.util.Arrays;

public class Main {

    static int nthLargest(final int[] arr, final int rank) {

        assert rank > 0;

        final int[] array = Arrays.stream(arr).map(i -> -i).sorted().distinct().limit(rank).toArray();

        return -array[Math.min(rank - 1, array.length - 1)];
    }

    public static void main(final String args[]) {

        System.out.println(nthLargest(new int[] { 1, 5, 2, 5, 10, 2, 2, 5, 10, 12, 25, 1, 5 }), 3);

    }
}

Другие вопросы по теме