Pythonで同等の頻度のシーケンスを見つけるプログラム

番号のリストがあるとします。シーケンスから番号を削除したときに、各番号が同じ回数発生するように、番号の最長シーケンスの長さを見つける必要があります。

したがって、入力が数値=[2、4、4、7、7、6、6]のような場合、出力は7になります。

これを解決するには、次の手順に従います-

• num_freq：=新しいマップ

• freq_freq：=新しいマップ

• diff_freq：=新しいセット

• 結果：=1

• インデックスIと値num（num）ごとに、実行します

  • 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

  • cur_freq+1をdiff_freqに追加します

  • cur_freqがdiff_freqにあり、freq_freq [cur_freq]が0と同じである場合、

    • diff_freqからcur_freqを削除します

  • df_list：=diff_freqsの要素を取得することによる新しいリスト

  • df_listのサイズが1と同じ場合、

    • 結果：=i + 1

  • それ以外の場合、df_listのサイズが2と同じ場合、および（[| freq_freq [df_list [0]] --freq_freq [df_list [1]] |、freq_freq [df_list [0]]、freq_freq [df_list [1]]のいずれか）は1）であり、（[| df_list [0] -df_list [1] |、df_list [0]、df_list [1]]）のいずれかが1）の場合、

    • 結果：=i + 1

• 結果を返す

理解を深めるために、次の実装を見てみましょう-

例

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

入力

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

出力

7