Python - 列表中K個最大元素及其索引

---

列表是Python中一種常用的可變資料型別，可以儲存異構資料。我們可以透過索引訪問列表元素。索引表示任何元素到第一個元素的距離；因此它從0開始。本文將探討如何查詢k個最大元素及其索引號。我們將通過幾種方法來實現這一點，例如暴力法、遞迴、heapq模組、Numpy庫、enumerate函式等。我們還將探討所用演算法的時間和空間複雜度。

使用暴力法

暴力法是解決任何問題的最簡單方法。這涉及到對問題進行幾乎沒有最佳化的思考。雖然這能得到不錯的結果，但在空間和時間複雜度方面需要進一步最佳化。

示例

在下面的程式碼中，我們定義了一個名為k_max_elements的函式，它將列表和值k作為引數。我們迭代k次，每次迭代都使用Python的“max”方法查詢最大元素。我們將值和索引追加到一個已初始化的列表中。在每次迭代中，我們將最大元素替換為'-inf'，以確保它不會在下次迭代中被計算。

def k_max_elements(lst, k):
    result = []
    for _ in range(k):
        max_value = max(lst)
        max_index = lst.index(max_value)
        result.append((max_value, max_index))
        lst[max_index] = float('-inf') 
    return result
lst = [10, 5, 8, 12, 3]
k = 3
result = k_max_elements(lst, k)
print(result)

輸出

[(12, 3), (10, 0), (8, 2)]

使用遞迴

遞迴是一種經典的解決問題的技術，它將一個大問題分解成更小的子問題。我們的目標是解決這些較小的子問題，最終解決更大的問題。在遞迴解決方案中，我們還定義了一個基本情況，當我們到達基本情況時，程式將終止。

示例

在下面的程式碼中，我們使用了遞迴方法來查詢k個最大元素。我們的基本情況是k=0。我們採用了自頂向下的方法，試圖透過遞迴呼叫函式到基本情況來遞迴地查詢最大元素。我們將元素和索引追加到一個已初始化的列表中並返回它。

def k_max_elements(lst, k):
    if k == 0:
        return []
    max_value = max(lst)
    max_index = lst.index(max_value)
    lst[max_index] = float('-inf') 
    remaining_max_elements = k_max_elements(lst, k - 1)
    return [(max_value, max_index)] + remaining_max_elements
lst = [7,5,4,8,9,6,2,1]
k = 4
print(f'The original list is: {lst}')
result = k_max_elements(lst, k)
print(f"The {k} maximum elements and the index are: {result}")

輸出

The original list is: [7, 5, 4, 8, 9, 6, 2, 1]
The 4 maximum elements and the index are: [(9, 4), (8, 3), (7, 0), (6, 5)]

使用Heapq模組

Python中的'heapq'模組為我們提供了應用堆演算法的實現。它提供了建立和操作堆資料結構的功能，我們可以使用這些功能來高效地查詢集合中最小的或最大的元素。堆是一種類似於二叉樹的資料結構，其中每個父節點的值小於或等於其子節點的值。它基於LIFO原則——“後進先出”。

示例

在下面的程式碼中，我們使用了'heapq'庫來查詢列表的k個最大元素。在自定義函式中，我們遍歷列表並將值和索引推入堆中，直到我們迭代k次。堆保持k個最小元素在根部，因此我們可以有效地跟蹤迄今為止遇到的k個最大元素。對於超過前k個的元素，我們將當前元素-值-索引元組推入結果堆中，並同時從堆中彈出最小元素。這確保了結果堆始終包含迄今為止遇到的k個最大元素。

import heapq

def k_max_elements(lst, k):
    result = []
    for i, value in enumerate(lst):
        if i < k:
            heapq.heappush(result, (value, i))
        else:
            heapq.heappushpop(result, (value, i))
    return sorted(result, reverse=True)

lst = [10, 5, 8, 12, 3]
k = 3
result = k_max_elements(lst, k)
print(f'The original list is: {lst}')
print(f"The {k} maximum elements and the index are: {result}")

輸出

The original list is: [10, 5, 8, 12, 3]
The 3 maximum elements and the index are: [(12, 3), (10, 0), (8, 2)]

使用Numpy陣列

Numpy是另一個開源庫，用於處理數值和科學計算。該庫提供了一個名為“argpartition”的函式，該函式返回列表中k個最大元素的索引。該函式根據第k個最大元素對列表進行分割槽，並返回已分割槽元素的索引。如果我們只對k個元素感興趣，我們可以使用索引屬性只提取k個元素。

示例

在下面的程式碼中，我們使用了Pandas的“argpartition”方法將列表分成兩部分，一部分包含k個最大元素的所有索引。接下來，我們使用索引屬性只提取k個元素。我們使用Python的列表推導方法將索引及其對應的元素追加到名為result的列表中。接下來，我們使用“sorted”方法對列表進行排序，並將引數'reverse=True'設定為確保它從高到低排序。

import numpy as np

def k_max_elements(lst, k):
    indices = np.argpartition(lst, -k)[-k:]
    result = [(lst[i], i) for i in indices]
    return sorted(result, reverse=True)

lst = [4567,7,443,456,56,5467,74]
k = 4
result = k_max_elements(lst, k)
print(f'The original list is: {lst}')
print(f"The {k} maximum elements and the index are: {result}")

輸出

The original list is: [4567, 7, 443, 456, 56, 5467, 74]
The 4 maximum elements and the index are: [(5467, 5), (4567, 0), (456, 3), (443, 2)]

• 時間複雜度：O(n + k * log(k))

• 空間複雜度：O(k)

使用Lambda和Enumerate方法

Lambda函式是Python中一種特殊的函式。它們是沒有名稱的函式。當我們想要將函式應用於可迭代物件並且確定我們不會在其他地方重用程式碼時，Lambda函式特別有用。使用lambda函式的主要優點是我們可以在一行中編寫簡潔的邏輯來應用某些操作。這使得程式碼可讀性較差，但程式碼行數較少。

示例

在下面的示例中，我們使用了‘sorted’，‘enumerate’和‘lambda’函式的組合來返回k個最大元素。我們將列表和值'k'傳遞給函式k_max_elements。在函式中，我們使用了lambda函式和enumerate將元素與索引關聯起來。我們使用sorted方法對列表進行排序。接下來，我們使用列表推導方法將值和索引追加到列表中。

def k_max_elements(lst, k):
    sorted_lst = sorted(enumerate(lst), key=lambda x: x[1], reverse=True)
    result = [(value, index) for index, value in sorted_lst[:k]]
    return result


lst = [45,7,4,46,56,5467,74]
k = 4
result = k_max_elements(lst, k)
print(f'The original list is: {lst}')
print(f"The {k} maximum elements and the index are: {result}")

輸出

The original list is: [45, 7, 4, 46, 56, 5467, 74]
The 4 maximum elements and the index are: [(5467, 5), (74, 6), (56, 4), (46, 3)]

• 時間複雜度：O(n * log(n))

• 空間複雜度：O(n)

使用Pandas庫

Pandas是Python中一個著名的開源庫。該庫旨在處理資料預處理和操作。Pandas主要處理Pandas序列和Pandas資料幀。它提供sort_values方法來將所有值從高到低排序。我們可以利用該方法來查詢k個最大元素。由於Pandas處理資料幀，我們可以一次處理多列，因此我們可以輕鬆跟蹤索引和元素。

示例

在下面的示例中，我們首先匯入了Pandas庫。接下來，我們建立了函式k_max_elements，該函式將列表和值'k'作為引數，並返回k個最大元素。我們使用Pandas的Dataframe方法建立一個數據幀，其中包含列表元素的索引和值。接下來，我們使用'nlargest'和'sort_values'方法查詢已排序的'k'個最大元素。我們使用zip方法解壓縮元素的值和索引並返回結果。

import pandas as pd

def k_max_elements(lst, k):
    df = pd.DataFrame({'value': lst, 'index': range(len(lst))})
    df = df.nlargest(k, 'value').sort_values('index')
    result = list(zip(df['value'], df['index']))
    return result


lst = [45,7,4,46,56,5467,74]
k = 4
result = k_max_elements(lst, k)
print(f'The original list is: {lst}')
print(f"The {k} maximum elements and the index are: {result}")

輸出

The original list is: [45, 7, 4, 46, 56, 5467, 74]
The 4 maximum elements and the index are: [(46, 3), (56, 4), (5467, 5), (74, 6)]

• 時間複雜度：O(n * log(k))

• 空間複雜度：O(n)

結論

本文講解了如何在列表中查詢k個最大元素及其索引。Python提供了多種方法來解決這個問題。我們可以使用遞迴、迴圈語句等來構建自定義邏輯。但是，Python還為我們提供了許多內建方法，可以幫助我們執行相同的操作。Numpy、Pandas和Heapq是使我們能夠執行此操作的庫和包的示例。但是，讀者應該注意，這些並不是唯一的方法。我們可以進行一些調整，包括將輸出更改為其他資料結構。