मान लीजिए हमारे पास विशिष्ट मानों की एक लिस्ट है और हम प्रत्येक संख्या को नॉन-डिक्रीजिंग क्रम में हटाना चाहते हैं। हमें संख्याओं के उनके डिलीशन के क्रम में इंडेक्स ढूंढने हैं।
उदाहरण के लिए, यदि इनपुट 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++
- अन्यथा, right[j] को sorted_inds में जोड़ें, larger[right[j]] += left का आकार - i, j++
- left[i:] को sorted_inds में जोड़ें
- right[j:] को sorted_inds में जोड़ें
- sorted_inds लौटाएं
- मुख्य मेथड में:
- larger := nums के आकार की लिस्ट, 0 से भरी हुई
- my_sort(range(0, nums का आकार)) कॉल करें
- num_larger_pairs := प्रत्येक (nums, larger) के लिए पेयर बनाएं और सॉर्ट करें
- num_larger_pairs में सभी e के लिए e[1] वाली लिस्ट लौटाएं
पायथन कार्यान्वयन
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]