Kiểm tra xem các phần tử của một mảng có thể được sắp xếp thỏa mãn điều kiện đã cho trong Python hay không

Giả sử chúng ta có một mảng được gọi là nums. Chúng ta phải kiểm tra xem liệu có thể sắp xếp lại các phần tử của nums sao cho nó tuân theo điều kiện -

Vì vậy, nếu đầu vào là nums =[8, -4, 4, -8], thì đầu ra sẽ là Đúng như thể chúng ta sắp xếp mảng như [-4, -8, 4, 8] cho i =0, nums [2 * 0 + 1] =2 * (-4) =-8 cho i =1, nums [2 * 1 + 1] =2 * 4 =8

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• freq:=một bản đồ chứa các phần tử của num và tần số của chúng
• đối với mỗi mục trong số được sắp xếp theo giá trị tuyệt đối của chúng, hãy thực hiện
  • nếu freq [item] là 0, thì
    • chuyển sang lần lặp tiếp theo
  • nếu freq [2 * item] là 0, thì
    • trả về Sai
  • freq [item]:=freq [item] - 1
  • freq [2 * item]:=freq [2 * item] - 1
• trả về True

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

[8, -4, 4, -8]

Đầu ra

True