📝
配列/ 文字列(基礎) ソート、カスタムソート、バケットソート
ソートをすることで、重複した要素を見つけやすくしたり最大最小を探したりとかするやつ
217. Contains Duplicate
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
std::sort(nums.begin(), nums.end());
for (int i = 1; i < nums.size(); i++){
if(nums[i] == nums[i-1]){
return true;
}
}
return false;
}
};
242, Valid Anagram
class Solution {
public:
bool isAnagram(string s, string t) {
sort(s.begin(), s.end());
sort(t.begin(), t.end());
return s == t;
}
};
カスタムソート
例題:バージョン番号が含まれるリストが与えられたとき、これらを適切な昇順でソートしてください。バージョン番号は「major.minor.patch」の形式で表される。
- 自分の回答
class Version:
def __init__(self, version):
self.major, self.minor, self.patch = map(int, version.split("."))
def __eq__(self, other):
return self.major == other.major and self.minor == other.minor and self.patch == other.patch
def __ne__(self, other):
return self.major != other.major or self.minor != other.minor or self.patch != other.patch
def __lt__(self, other):
self_version = [self.major, self.minor, self.patch]
other_version = [other.major, other.minor, other.patch]
for i in range(3):
if self_version[i] < other_version[i]:
return True
if self_version[i] > other_version[i]:
return False
return False
def __le__(self, other):
self_version = [self.major, self.minor, self.patch]
other_version = [other.major, other.minor, other.patch]
for i in range(3):
if self_version[i] < other_version[i]:
return True
if self_version[i] > other_version[i]:
return False
return True
def __gt__(self, other):
self_version = [self.major, self.minor, self.patch]
other_version = [other.major, other.minor, other.patch]
for i in range(3):
if self_version[i] > other_version[i]:
return True
if self_version[i] < other_version[i]:
return False
return False
def __ge__(self, other):
self_version = [self.major, self.minor, self.patch]
other_version = [other.major, other.minor, other.patch]
for i in range(3):
if self_version[i] > other_version[i]:
return True
if self_version[i] < other_version[i]:
return False
return True
versions = []
for _ in range(int(input())):
v = Version(input())
versions.append(v)
versions.sort()
- 解説
やり方は以下の2つ.
from typing import List
def sort_versions(versions: List[str]) -> List[str]:
def verison_num_list(version):
return [int(v) for v in version.split('.')]
// sortのkeyを変換する.
versions.sort(key=verison_num_list)
return versions
print(sort_versions(["10.1.0", "1.1.0", "0.1.1"])) # ['0.1.1', '1.1.0', '10.1.0']
print(sort_versions(["0.12.1", "0.2.1"])) # ['0.2.1', '0.12.1']
from functools import cmp_to_key
// cmpt_to_keyを使う, 前後比較が複雑な場合はこっち.
def sort_versions(versions: List[str]) -> List[str]:
def compare(v1, v2):
a = [int(v) for v in v1.split('.')]
b = [int(v) for v in v2.split('.')]
if a == b:
return 0
elif a < b:
return -1
else:
return 1
versions.sort(key=cmp_to_key(compare))
return versions
print(sort_versions(["10.1.0", "1.1.0", "0.1.1"])) # ['0.1.1', '1.1.0', '10.1.0']
print(sort_versions(["0.12.1", "0.2.1"])) # ['0.2.1', '0.12.1']
Custom Sort String
class Solution:
def customSortString(self, order: str, s: str) -> str:
def returnIndex(c):
if c in dic:
return dic[c]
else:
return float('inf')
dic = {}
for i in range(len(order)):
dic[order[i]] = i
list_s = list(s)
list_s.sort(key = returnIndex)
return "".join(list_s)
例題と一緒
Sort the Jumbled Numbers
class Solution:
def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
def generateKey(num):
if num == 0:
return mapping[0]
newKey = []
while num:
amari = num % 10
num = num // 10
newKey.append(str(mapping[amari]))
newKey.reverse()
return int("".join(newKey))
nums.sort(key = generateKey)
return nums
pythonだと"007"みたいな文字列もint(s)で変換させるとちゃんと7にしてくれるからこの実装で大丈夫だけど、あんまり文字列変換処理噛ませたくないなら以下.
class Solution:
def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
def generateKey(num):
if num == 0:
return mapping[0]
newKey = 0
factor = 0
while num:
amari = num % 10
num = num // 10
newKey += mapping[amari] * (10 ** factor)
factor += 1
return newKey
nums.sort(key = generateKey)
return nums
Largest Number
別にintをstrで扱ってもいい. 注意しなきゃいけないのは先頭に0が来る時だけ.
from functools import cmp_to_key
class Solution:
def largestNumber(self, nums):
def compare(a: str, b: str):
# 2つの文字列 a と b を異なる順序で連結し、その結果を比較する
# a + b と b + a を比較し、より大きい方が最適な順序を決定する
# b + a < a + b の場合、a を b の前に置く方が大きな数を生成する
# この場合は-1を返して、a を b の前にソートする
# そうでなければ1を返して、b を a の前にソートする
return -1 if b + a < a + b else 1
str_nums = [str(n) for n in nums]
largest_num = "".join(sorted(str_nums, key=cmp_to_key(compare)))
return "0" if largest_num[0] == "0" else largest_num
最初普通に3と35だったら,3に3を補って比較みたいなことしたけど、これは他の値によるからだめ. 普通に2つの数字同士を繋げて大きい方でいい.
from functools import cmp_to_key
class Solution:
def largestNumber(self, nums: List[int]) -> str:
def convertToList(num):
if num == 0:
return [0]
l = []
while num:
amari = num % 10
l.append(amari)
num = num // 10
l.reverse()
return l
def compare(num1, num2): #num1 < num2→-1 , else →1
l1 = convertToList(num1)
l2 = convertToList(num2)
for i in range(max(len(l1), len(l2))):
u = l1[i] if i < len(l1) else l1[0]
v = l2[i] if i < len(l2) else l2[0]
if u < v:
return -1
if u > v:
return 1
return 0
nums.sort(key=cmp_to_key(compare), reverse=True)
nums = [str(num) for num in nums]
return "".join(nums)
Sort Characters By Frequency
from collections import defaultdict
class Solution:
def frequencySort(self, s: str) -> str:
dic = defaultdict(int)
l = []
for c in s:
if not c in dic:
l.append(c)
dic[c] += 1
l.sort(key = lambda x:dic[x], reverse = True)
ans = []
for c in l:
ans += [c for _ in range(dic[c])]
return "".join(ans)
keyを頻度にするだけ. バケットソート的な考え方でもできるぽい.
Discussion