2

Нужно из заданного массива найти значения четырех максимальных элементов, т.е. например из массива {1,2,3,4,5,6} нужно вывести {3,4,5,6} на языке Java.

Как один элемент вывести я знаю, а вот как остальные вывести?

public class massive1 {
    public static void main(String[] args) {
        System.out.println("Массив: ");
        int[] mas1 = {10,20,30,40,50,60};
        for (int i=0; i<=mas1.length - 1; i++)
        {
            System.out.println(mas1[i] + " ");
        }
        int max1 = mas1[0];
        for (int i=1; i<mas1.length; i++)
        {
            if (mas1[i]>max1)
            {
                max1 = mas1[i];
            }
        }
        System.out.print("Максимальное значение в массиве: " + max1);
    }
}
1
  • 5
    отсортируй массив и возьми последние 4 элемента
    – Grundy
    10 ноя 2016 в 7:43

5 ответов 5

4
int[] mas1 = {10,20,30,40,50,60};//объявил массив
    Arrays.sort(mas1);//отсортировал (не забудь import java.util.Arrays;)
    for (int i = mas1.length - 4; i < mas1.length; i++)//вместо 4 подставляешь сколько последних элементов выводить
        System.out.println(mas1[i]);//выводишь
2
  • Как предложил @Grundy: отсортировать и вывести последние 4 элемента

  • Есть вариант предложенный на английской версии, использовать алгоритм выбора для нахождения k-го по величине элемента в массиве, а затем вывести все элементы, которые больше найденного

  • Из того-же вопроса на английской версии другой вариант:

    Использовать список: вставляем n-элементов, далее, если следующий элемент больше минимального, вставляем новый и удаляем минимальный

1

Можно использовать порядковую статистику.

Рекурсивно делим подмассив на две части. Берем из подмассива некоторый опорный элемент (pivot), и делим подмассив на то, что больше опорного элемента, и меньше. Если тех, которые больше оказалось больше чем нужно, рекурсивно обрабатываем правую часть, если меньше - левую, если сколько нужно - ответ найден.

Алгоритм деления (partition) тот же самый, что в быстрой сортировке (quicksort) используется, разница в том, что делится только одна ветвь.

Лучшее и среднее время - O(n), худшее - O(n^2),

Методы лечения те же, что и у quicksort - правильный выбор pivot. Можно выбирать случайно.

Смотрите так же: k-я порядковая статистика, медиана.

Сам алгоритм называется quickselect.

0

У меня получилось такое решение:

private static <T extends Comparable<? super T>> Collection<T> getOrderStatistics(Collection<T> elements, int maxCount) {
    PriorityQueue<T> queue = new PriorityQueue<>(maxCount);
    for (T element : elements)
        if (queue.size() < maxCount)
            queue.add(element);
        else if (queue.peek().compareTo(element) < 0) {
            queue.poll();
            queue.add(element);
        }

    return queue;
}

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

0

разобрался, вот, может кому и поможет))

    public static int[] MaxElements(int[] arr){
    boolean sorted = true;
    int buf = 0;
    for (int j=0; j<arr.length; j++) {
        for (int i = 0; i < arr.length - 1; i++) {
            sorted = true;
            if (arr[i] < arr[i + 1]) {
                buf = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = buf;
                buf = 0;
            }
        }
    }

    int[] arr1 = {0,0,0,0,0};
    for (int i=0; i<5; i++){
        arr1[i] = arr[i];
    }

    return arr1;
}
2
  • что должен был делать флаг sorted? у него всегда значение true, но и оно нигде не проверяется
    – Grundy
    24 ноя 2016 в 12:45
  • Лучше используйте стандартную сортировку, чем свои костыли :)
    – gil9red
    24 ноя 2016 в 12:58

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.