【LeetCode】 1207. Unique Number of Occurrences 解答・解説【Python】

はじめに
1. ポイント
詳細
1. 問題
  1. 原文
  2. 内容(和訳)
2. 解答
  1. 解答1：Python, set, dict
終わりに
1. 補足・参考・感想
2. 他の問題もどうぞ

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

様々なカテゴリの問題をランダムにあたる方法も良いですが、

二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。

テーマごとに問題を分類しました。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

ポイント

- set
- 辞書

詳細

問題

原文

Given an array of integers arr, return true if the number of occurrences of each value in the array is unique or false otherwise.

Example 1:

Input: arr = [1,2,2,1,1,3] Output: true Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

1
2
3

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

Example 2:

Input: arr = [1,2] Output: false

1
2

Input: arr = [1,2]
Output: false

Example 3:

Input: arr = [-3,0,1,-3,1,1,1,-3,10,0] Output: true

1
2

Input: arr = [-3,0,1,-3,1,1,1,-3,10,0]
Output: true

Constraints:

1 <= arr.length <= 1000

-1000 <= arr[i] <= 1000

内容(和訳)

整数配列arrが与えられます。

各要素の発生回数が全て異なっていればTrue、そうでなければFalseを返してください。

※正しくない可能性があります。

解答

解答1：Python, set, dict

class Solution:
    def uniqueOccurrences(self, arr: List[int]) -> bool:
        elements = list(set(arr))
        count_dict = {}
        for i in range(len(elements)):
            count_dict[elements[i]] = 0
        print(count_dict)
        
        for i in range(len(elements)):
            for j in range(len(arr)):
                if elements[i] == arr[j]:
                    count_dict[elements[i]] += 1
        
        if len(set(count_dict.values())) == len(count_dict.values()):              
            return True 
        else:
            return False

class Solution:

def uniqueOccurrences(self, arr: List[int]) -> bool:

elements = list(set(arr))

count_dict = {}

for i in range(len(elements)):

count_dict[elements[i]] = 0

print(count_dict)

for i in range(len(elements)):

for j in range(len(arr)):

if elements[i] == arr[j]:

count_dict[elements[i]] += 1

if len(set(count_dict.values())) == len(count_dict.values()):

return True

else:

return False

arrの重複のない各要素をsetで取得してelementsに保持。

elementsの各要素が、arrの各要素と一致したらその発生回数をcount_dictに記録する。

elementsの各要素を一巡し、さらにarrの各要素を一巡して走査するので、時間計算量はO(n^2)。

elementsの要素数だけ辞書と配列を用意するので空間計算量はO(n)。

要改善。

終わりに

補足・参考・感想

問題を分類しました。テーマごとに集中して問題を解くことができます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。

解答前に知っておくと役に立つかもしれない情報

他の問題もどうぞ

前：724. Find Pivot Index

次：649. Dota2 Senate

LeetCode 解答・解説記事一覧