はじめに
LeetCodeの問題を解答します。
なるべく、問題の和訳と詳細なコメントを書いています。
余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。
様々なカテゴリの問題をランダムにあたる方法も良いですが、
二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。
テーマごとに問題を分類しました。
LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。
また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。
LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。
はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。
ポイント
-
- set
- 辞書
詳細
問題
原文
Given an array of integers
arr
, returntrue
if the number of occurrences of each value in the array is unique orfalse
otherwise.
Example 1:
123 Input: arr = [1,2,2,1,1,3]Output: trueExplanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.Example 2:
12 Input: arr = [1,2]Output: falseExample 3:
12 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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に特有の内容など、知っておくと役に立つかもしれないことをまとめました。
他の問題もどうぞ
コメント