Поиск четвертого по величине и четвертому наименьшему числу в массиве

Я попробовал следующий метод, чтобы найти второе по величине и наименьшее число, и он работает:

class Test

{

static void main()throws IOException

{
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter");
    int a[] = {45,79,2,5,74,4,19,56,2,888};
    int small= a[0];
    int big=a[0];
    int s=0,b=0;
    for(int i=0;i<10;i++)
    {
        if(small>a[i])
        {
            small=a[i];
        }
        if(big<a[i])
        {
            big=a[i];
        }
    }

    int small2=a[0],big2=a[0];

    for(int i=0;i<10;i++)
    {
        if(small2>a[i]&&a[i]!=small)
        {
            small2=a[i];
        }
        if(big2<a[i]&&a[i]!=big)
        {
            big2=a[i];
        }
    }
    System.out.println("second biggest = "+big2);
    System.out.println("second smallest = "+small2);
}
}

Теперь я хочу найти четвертый самый большой и самый низкий. в этом случае мне, вероятно, нужно использовать 4 петли. но я хочу сделать это короче, умнее. Может ли кто-нибудь помочь?

java,arrays,sorting,

-1

Ответов: 6

3 принят

вот несколько решений:

  1. если вы не хотите сортировать весь ввод, вы можете поместить временную коллекцию, которую вы хотите отсортировать (или использовать ту, которая уже всегда сортируется).

    например, если вход «1,2,3,4,5,6,7,8,9, ... 1000», и вы хотите получить наибольшее число m-th, вы создаете временную коллекцию размер m, и каждый номер, который вы проходите, вы решаете, должен ли он находиться во временном массиве или нет. вы всегда должны сортировать временную коллекцию (или просто использовать ту, которая уже всегда сортируется), и вставлять в нее новый элемент, удаляя самый маленький, если его размер превышает m.

    с точки зрения памяти вы используете небольшой размер элементов коллекции (m), и вы не изменяете входной массив.

    с точки зрения количества операций (сложности), вы получаете примерно то же, что и для сортировки массива - O (nlogn), потому что для каждого элемента, который вы помещаете в массив temp, коллекции нужно, куда его поместить, и который принимает logn ( используя двоичный поиск, например).

    Кстати, это решение примерно такое же, как и получение самого большого / наименьшего числа, просто вам не нужно сортировать элементы во временной коллекции, потому что это размер 1.

  2. если вам не нужна память, но вы просто не хотите менять ввод, вы можете сделать копию массива и отсортировать его вместо этого ...

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

2

Вы можете использовать общий путь. Содержите массив, используя, Arrays.sort(array);а затем вы можете получить к нему доступ с помощью индекса.

2

Я думаю, что самый простой способ - упорядочить массив (это Log (n)).

Если вы не хотите изменять исходный массив, вы можете сделать клон первым (int b [] = Arrays.copyOf (a, a.length);).

Если вы хотите, чтобы позиция в массиве вместо значения сообщила мне, и я найду другое решение.

Скажите, если это поможет:

    public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    System.out.println("Enter");
    int a[] = { 45, 79, 2, 5, 74, 4, 19, 56, 2, 888 };

    Arrays.sort(a);
    System.out.print("ordered array: ");
    for(int i:a){
        System.out.print(i+", ");
    }
    System.out.println();
    System.out.println("the 4th smallest : " + a[3]);
    System.out.println("the 4th biggest: " + a[(a.length - 4)]);

}
2

Сортировка общего массива - O (nlogn), а затем вы можете просто выбрать свой элемент по индексу.

Вы также можете использовать алгоритм Select, который имеет сложную временную сложность O (n). Алгоритм получает массив и некоторый k и возвращает k-ый большой элемент. Я уверен, вы можете найти его реализацию.

1 
public class FourthLargest {

    static int a[] = {45, 79, 2, 5, 74, 4, 19, 56, 2, 888};

    public static void main(String[] args) {
        Arrays.sort(a);
        System.out.println("The fourth smallest number = " + a[3]);
        System.out.println("The fourth largest number = " + a[a.length-4]);
    }
}
Java, массивы, сортировка,
Похожие вопросы
Яндекс.Метрика