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 you have read our privacy policy.

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