Печатайте самые большие значения списка в том же порядке, не создавая новый список

Question

Здесь у меня есть список

[9,1,2,11,8]

Мне нужно напечатать верхние 3 в этом списке, например,

[9,11,8]

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

Answer 1

Я попытался создать пример программы, основанной на вводе и выводе, которые вы запрашивали.Я думал о том, чтобы попробовать.Пожалуйста, не стесняйтесь оптимизировать или оставить отзыв.Я попытался объяснить шаги в самом коде.Спасибо.

package com.test;

import java.util.ArrayList;
import java.util.List;

public class ArrangeList {
    public static void main(String[] args) {
        List<Integer> givenList = new ArrayList<>();
        givenList.add(9);
        givenList.add(1);
        givenList.add(2);
        givenList.add(11);
        givenList.add(8);

        int currentIndex = 0; //gives the current index
        while (givenList.size() != 3) {
            int nextIndex = currentIndex + 1; //gives you the next index 
            int currentValue = givenList.get(currentIndex); //gives you the current value for the current index 
            int nextValue = givenList.get(nextIndex); //gives you the next value for the next index

            if (nextValue < currentValue) { //check if the next value is greater than current value. If true, then remove the next value from the list
                givenList.remove(nextIndex);
            } else {
                currentIndex++; //increment the index if you if the current value is greater than the upcoming value from the list
            }

        }
        System.out.println(givenList); //prints the values stored in the list

    }
}

Вывод после выполнения программы:

[9, 11, 8]

Answer 2

Вы также можете реализовать класс-оболочку для вашего списка.Есть личные данные членов (в вашем случае 3) для самых больших значений в списке.Обновите эти переменные после выполнения вставки и удаления.

Answer 3

def k_largest(iterable, k=3):
    it = iter(iterable)
    result = [next(it) for _ in range(k)] # O(k) space
    r_min = min(result)
    for elem in it:
        if elem > r_min:
            result.remove(r_min)  # O(n*k) time
            result.append(elem)
            r_min = min(result)
    return result

Первое значение выигрывает в случае ничьей.Если вы хотите, чтобы последнее значение выиграло, просто измените > на >=.

. Это хороший подход для больших данных и небольших выборок, т. Е. Где n >> k, где n - длина вводаи k является выбранным числом.В этом случае термин k не имеет значения, поэтому подход равен O (n) сложность по времени, что благоприятно для O (n log n) подходов на основе сортировки.Если k большое, это больше не будет хорошим решением.Вы должны посмотреть на поддержание отсортированного набора результатов, разделив его пополам для вставки и, возможно, используя быстрый выбор , чтобы найти максимумы.

Другая опция, которая имеет более простой код, доступна с использованием Python stdlib heapq.nlargest, хотя на практике это может быть медленнее:

import heapq
from operator import itemgetter

def k_largest_heap(iterable, k=3):
    ks = heapq.nlargest(k, enumerate(iterable), key=itemgetter(1))
    return [k for i, k in sorted(ks)]

I думаю это O (n log (k)) ,хотя по общему признанию я достигаю краев своих знаний здесь.

Некоторые моменты времени со списком из 10 000 целых чисел:

from random import randint
nums =  [randint(1, 10000) for _ in range(10000)]
%timeit k_largest(nums)
# 331 µs ± 4.69 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit k_largest_heap(nums)
# 1.79 ms ± 27.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit top_three(nums)
# 1.39 ms ± 16.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Примечание: top_three реализациярешение от пользователя Delirious Lettuce здесь .

Answer 4

РЕДАКТИРОВАТЬ:

Мне любопытно, почему меня понижают.Решение @wim охотно игнорирует ограничение в первоначальном вопросе «без составления нового списка».Единственный ответ состоял в том, чтобы временно изменить его на deque в странной попытке обойти это ограничение.В настоящее время это единственный ответ, который соответствует всем требованиям ОП (перечислены ниже как два отдельных комментария).

---

Печатать самые большие значения списка в том же порядке, не создавая новый список

Мне нужно напечатать верхние 3 в этом списке, например

В этом ответе предполагается, что число всегда равно трем для того, сколько верхних чисел вам нужно извлечь, в их оригиналепорядок.Если это так, то, похоже, ответом будет O(n) время и O(1) пространство.

def top_three(nums):
    if len(nums) <= 3:
        return nums

    a = b = c = float('-inf')
    dex_a = dex_b = dex_c = None
    for i, num in enumerate(nums):
        if num > a and num > b and num > c:
            a, b, c = num, a, b
            dex_a, dex_b, dex_c = i, dex_a, dex_b
        elif num > b and num > c:
            b, c = num, b
            dex_b, dex_c = i, dex_b
        elif num > c:
            c = num
            dex_c = i

    if dex_a < dex_b < dex_c:
        print(a, b, c)
    elif dex_a < dex_c < dex_b:
        print(a, c, b)
    elif dex_b < dex_a < dex_c:
        print(b, a, c)
    elif dex_b < dex_c < dex_a:
        print(b, c, a)
    elif dex_c < dex_a < dex_b:
        print(c, a, b)
    elif dex_c < dex_b < dex_a:
        print(c, b, a)

Тесты:

In[3]: top_three([9, 1, 2, 11, 8])
9 11 8
In[4]: top_three([9, 1, 2, 11, 8, 9])
9 11 9
In[5]: top_three([3, 3, 1, 0, 4, 3, 2, 5])
3 4 5

Answer 5

Я бы изменил select-sort , чтобы захватывать (n) как MAX вместо одного.и вместо запуска n2 просто зайдите в список один раз.

, поэтому [9,1,2,11,8]

вы бы инициализировали со списком MAX [0,0,0], затем циклически перебирайте в своем списке вещи, которые больше, чем MAX

1. [9,0,0]
2. [9,1,0]
3. [9,1,2]
4. [9,11,2]
5. [9,11,8]

самая сложная часть - шаг 4, где вам нужнорешить оставить 9 и 2 и заменить 1 на 11.