📝

配列/ 文字列(基礎) ソート、カスタムソート、バケットソート

2024/10/07に公開

ソートをすることで、重複した要素を見つけやすくしたり最大最小を探したりとかするやつ

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