Chương trình tìm ra một chuỗi có tần suất tương đương trong Python

Giả sử chúng ta có một danh sách các số. Chúng ta phải tìm độ dài của dãy số dài nhất sao cho khi chúng ta xóa một số khỏi dãy, mỗi số xuất hiện cùng một số lần.

Vì vậy, nếu đầu vào là số =[2, 4, 4, 7, 7, 6, 6], thì đầu ra sẽ là 7.

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

• num_freq:=một bản đồ mới

• freq_freq:=một bản đồ mới

• diff_freq:=một tập hợp mới

• kết quả:=1

• đối với mỗi chỉ mục I và giá trị num tính bằng nums, thực hiện

  • cur_freq:=num_freq [num]

  • num_freq [num]:=num_freq [num] + 1

  • freq_freq [cur_freq]:=freq_freq [cur_freq] - 1

  • freq_freq [cur_freq + 1]:=freq_freq [cur_freq + 1] + 1

  • thêm cur_freq + 1 vào diff_freq

  • nếu cur_freq nằm trong diff_freq và freq_freq [cur_freq] bằng 0 thì

    • xóa cur_freq khỏi diff_freq

  • df_list:=một danh sách mới bằng cách lấy các phần tử của diff_freqs

  • nếu kích thước của df_list bằng 1 thì

    • kết quả:=i + 1

  • ngược lại khi kích thước của df_list bằng 2 và (khi bất kỳ [| freq_freq [df_list [0]] - freq_freq [df_list [1]] |, freq_freq [df_list [0]], freq_freq [df_list [1]]) là 1) và (khi bất kỳ [| df_list [0] -df_list [1] |, df_list [0], df_list [1]]) là 1), thì

    • kết quả:=i + 1

• trả về kết quả

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

Ví dụ

from collections import defaultdict
class Solution:
   def solve(self, nums):
      num_freq = defaultdict(int)
      freq_freq = defaultdict(int)
      diff_freq = set()
      result = 1
      for i, num in enumerate(nums):
         cur_freq = num_freq[num]
         num_freq[num] += 1
         freq_freq[cur_freq] −= 1
         freq_freq[cur_freq + 1] += 1
         diff_freq.add(cur_freq + 1)
         if cur_freq in diff_freq and freq_freq[cur_freq] == 0:
            diff_freq.remove(cur_freq)
         df_list = list(diff_freq)
         if len(df_list) == 1:
            result = i + 1
         elif (
            len(df_list) == 2
            and any(
               x == 1
               for x in [
                  abs(freq_freq[df_list[0]] − freq_freq[df_list[1]]),
                  freq_freq[df_list[0]],
                  freq_freq[df_list[1]],
               ]
            )
            and any(x == 1 for x in [abs(df_list[0] − df_list[1]), df_list[0], df_list[1]])
            ):
            result = i + 1
      return result
ob = Solution()
print(ob.solve([2, 4, 4, 7, 7, 6, 6]))

Đầu vào

numbers = [2, 4, 4, 7, 7, 6, 6]

Đầu ra

7