पायथन में जांचें कि सरणी के तत्वों को दी गई शर्त को पूरा करने के लिए व्यवस्थित किया जा सकता है या नहीं

मान लीजिए हमारे पास nums नामक एक सरणी है। हमें जांचना है कि क्या nums के तत्वों को इस तरह पुनर्व्यवस्थित करना संभव है कि यह शर्त का पालन करे:

इसलिए, यदि इनपुट nums = [8, -4, 4, -8] है, तो आउटपुट True होगा क्योंकि यदि हम सरणी को [-4, -8, 4, 8] की तरह व्यवस्थित करते हैं, तो i = 0 के लिए, nums[2*0 + 1] = 2 * (-4) = -8, i = 1 के लिए, nums[2*1 + 1] = 2 * 4 = 8

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• freq := nums के तत्वों और उनकी आवृत्तियों वाला मैप
• nums में प्रत्येक आइटम के लिए उनके निरपेक्ष मानों में क्रमबद्ध, करें
  • यदि freq[item] 0 है, तो
    • अगले पुनरावृत्ति के लिए जाएं
  • यदि freq[2 * item] 0 है, तो
    • False लौटाएं
  • freq[item] := freq[item] - 1
  • freq[2 * item] := freq[2 * item] - 1
• True लौटाएं

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

from collections import defaultdict
def solve(nums):
    freq = defaultdict(int)
    for item in nums:
        freq[item] += 1
    for item in sorted(nums, key=abs):
        if freq[item] == 0:
            continue
        if freq[2 * item] == 0:
            return False
        freq[item] -= 1
        freq[2 * item] -= 1
    return True
nums = [8, -4, 4, -8]
print(solve(nums))

इनपुट

[8, -4, 4, -8]

आउटपुट

True