我有一個整數陣列。我想找到差異為 1 的所有唯一集，并將它們分成唯一集。
示例輸入：[3,4,5,8,9,11]
示例輸出：[{3,4,5}, {8,9}, {11}]
用 Python 最簡單的方法是什么？
uj5u.com熱心網友回復：
抓住鏈的開頭并將鏈的所有元素添加到一個集合中。
這是這個想法的超級簡單代碼：
def f(arr):
res = []
st = set(arr)
for num in st:
if num - 1 not in st: #begin of chain
temp = []
while num in st:
temp.append(num)
num = 1
res.append(temp)
return res
print(f([3,4,5,8,9,11]))
Output: [[3, 4, 5], [8, 9], [11]]
Time complexity: O(n)
Space complexity: O(n)
我想這是我們能達到的最好的復雜性。（不要介意代碼中的變數名??）
我假設您輸入的串列不包含重復項。如果輸入是 [3,4,5,8,9,11,8,9,10] 我們是否想要唯一的集合為 [[3,4,5],[8,9,10,11],[8, 9]]？如果是，那么我把它留給你作為練習。提示：使用計數器/字典而不是上面的設定，這很容易。
uj5u.com熱心網友回復：
也許不是最有效的，但您可以排序，然后根據差異進行拆分。這是使用 numpy 的解決方案：
example_input = [3, 4, 5, 8, 9, 11]
output = np.split(np.sort(example_input),
np.where(np.diff(np.sort(example_input)) > 1)[0] 1)
這樣做是找出排序陣列元素之間的差異大于 1 的位置，然后將輸入拆分。我們將一個添加到元素以在下一組拆分。
然后，如果您愿意，可以將陣列映射到集合。
sets = [set(x) for x in output]
# [{3, 4, 5}, {8, 9}, {11}]
uj5u.com熱心網友回復：
- 您可以從第一個數字開始并繼續將其遞增 1，直到您獲得的新值不再位于原始串列中。
- 洗掉原始串列中的值。
- 對剩余的值重復相同的程序。
這應該讓你開始
import typing
def find_unique(elems: list[int]) -> set[int]:
... # fill in your code here
def find_all_unique(elems: list[int]) -> typing.Iterator[set[int]]:
while (elems):
yield find_unique(elems)
if __name__ == '__main__':
my_list = [3,4,5,8,9,11]
print list(find_all_unique(my_list))
uj5u.com熱心網友回復：
s您可以先對輸入串列進行排序，然后使用第一個元素初始化一個集合。
然后遍歷第二個到最后一個元素的排序串列，將數字num與其前一個數字進行比較prev_num。
- 如果
num == prev_num（如果輸入串列包含重復項），那么我們就忽略它。 - 如果
num == prev_num 1，那么我們添加num到同一個集合s - 否則，我們知道我們需要創建一個新集合。我們將當前集合添加到輸出串列并創建一個新集合。
def find_unique_sets(input_list):
output_list = []
if not input_list:
return output_list
input_list.sort()
s = {input_list[0]}
prev_num = input_list[0]
for i in range(1, len(input_list)):
num = input_list[i]
if num == prev_num:
continue
elif num == prev_num 1:
s.add(num)
else:
output_list.append(s)
s = {num}
prev_num = num
output_list.append(s)
return output_list
print(find_unique_sets([3,4,5,8,9,11]))
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/492018.html
標籤：Python python-3.x 算法
上一篇：python中字串中的元音組