描述
a我有一個包含 N 個整數元素的陣列，范圍從 0 到 M-1。我有另一個b帶有 N 個正數的陣列。
然后，我想創建一個c包含 M 個元素的陣列。c其索引的第 i 個元素的a值為 i。
- 如果存在多個這些指數，那么我們取 中值較高的一個
b。 - 如果不存在，則 的第 i 個元素
c應為 -1。
例子
N = 5，M = 3
a = [2, 1, 1, 2, 2]
b = [1, 3, 5, 7, 3]
那么，c應該是...
c = [-1, 5, 7]
我的解決方案 1
一種可能的方法是初始化一個d存盤當前最大值的陣列，然后回圈a并b更新最大值。
c = -np.ones(M)
d = np.zeros(M)
for i, (idx, val) in enumerate(zip(a, b)):
if d[idx] <= val:
c[idx] = i
d[idx] = val
這個解決方案在時間上是 O(N)，但需要用 Python 迭代陣列，這使得它很慢。
我的解決方案 2
另一種解決方案是a使用b作為鍵進行排序。然后，我們可以將a索引分配給c（最大元素將是最后一個）。
sort_idx = np.argsort(b)
a_idx = np.arange(len(a))
a = a[sort_idx]
a_idx = a_idx[sort_idx]
c = -np.ones(M)
c[a] = a_idx
此解決方案不需要 Python 回圈，但需要排序b，使其成為 O(N*log(N))。
理想的解決方案
是否可以在線性時間內解決這個問題，而不必在 Python 中回圈陣列？
uj5u.com熱心網友回復：
AFAIK，目前無法在O(n)Numpy 中實作（主要是因為索引表是關于另一個陣列的值的讀取和寫入）。請注意，np.argsort(b)理論上可以O(n)使用基數排序來實作，但是這種排序在 Numpy 中還沒有實作（由于演算法在大陣列上的快取區域性不好，實際上它不會快得多）。
一種解決方案是使用Numba來加速您的演算法高效解決方案。Numba 使用 JIT 編譯器來加速回圈。這是一個示例（使用np.int32型別）：
import numpy as np
import numba as nb
@nb.njit('int32[:](int32[:], int32[:])')
def compute(a, b):
c = np.full(M, -1, dtype=np.int32)
d = np.zeros(M, dtype=np.int32)
for i, (idx, val) in enumerate(zip(a, b)):
if d[idx] <= val:
c[idx] = i
d[idx] = val
return c
a = np.array([2, 1, 1, 2, 2], dtype=np.int32)
b = np.array([1, 3, 5, 7, 3], dtype=np.int32)
c = compute(a, b)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/433827.html