資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：刪除元素後獲取列表索引（升序刪除）
假設我們有一個包含不同值的列表，我們希望按非遞減順序刪除每個數字。我們必須找到按刪除順序排列的數字的索引。
因此，如果輸入類似於 nums = [4, 6, 2, 5, 3, 1]，則輸出將為 [5, 2, 3, 0, 1, 0]，因為我們刪除 1，所以陣列為 [4, 6, 2, 5, 3]，然後刪除 2，陣列為 [4, 6, 5, 3]，然後刪除 3 我們得到 [4, 6, 5]，然後刪除 4 我們得到 [6, 5]，刪除 5，[6]，最後刪除 6。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式 my_sort()。這將接收 inds
- 如果 inds 的大小 <= 1，則
- 返回 inds
- sorted_inds := 一個新的列表
- mid := inds 的大小 / 2
- left := my_sort(inds[從索引 0 到 mid])，right := my_sort(inds[從索引 mid 到結尾])
- i := 0，j := 0
- 當 i < left 的大小 且 j < right 的大小 時，執行
- 如果 nums[left[i]] < nums[right[j]]，則
- 將 left[i] 插入 sorted_inds 的末尾
- i := i + 1
- 否則，
- 將 right[j] 插入 sorted_inds 的末尾
- larger[right[j]] := larger[right[j]] + left 的大小 - i
- j := j + 1
- 如果 nums[left[i]] < nums[right[j]]，則
- 將 left[從索引 i 到結尾] 插入 sorted_inds
- 將 right[從索引 j 到結尾] 插入 sorted_inds
- 返回 sorted_inds
- 從主方法執行以下操作：
- larger := 一個大小為 nums 的新列表，並填充 0
- my_sort(範圍 0 到 nums 的大小)
- num_larger_pairs := 為每個 (nums, larger) 建立對並排序它們
- 返回一個列表，其中包含所有 e in num_larger_pairs 的 e[1]
示例（Python）
讓我們看看以下實現以更好地理解：
class Solution: def solve(self, nums): return solve(nums) def solve(nums): def my_sort(inds): if len(inds) <= 1: return inds sorted_inds = [] mid = len(inds) // 2 left, right = my_sort(inds[:mid]), my_sort(inds[mid:]) i = j = 0 while i < len(left) and j < len(right): if nums[left[i]] < nums[right[j]]: sorted_inds.append(left[i]) i += 1 else: sorted_inds.append(right[j]) larger[right[j]] += len(left) - i j += 1 sorted_inds.extend(left[i:]) sorted_inds.extend(right[j:]) return sorted_inds larger = [0] * len(nums) my_sort(range(len(nums))) num_larger_pairs = sorted(zip(nums, larger)) return [e[1] for e in num_larger_pairs] ob = Solution() nums = [4, 6, 2, 5, 3, 1] print(ob.solve(nums))
輸入
[4, 6, 2, 5, 3, 1]
輸出
[5, 2, 3, 0, 1, 0]
更新於：2020年12月12日
瀏覽量：143
廣告