[hackerrank][python] Cut the sticks

題目連結: https://www.hackerrank.com/challenges/cut-the-sticks/problem

這題一開始想法基本上都差不多，就是把最小找出來後，去除掉再算整個 list 的長度，一開始我想利用建 table 來加速，不過好像時間複雜度反而沒有比較好XD

def cutTheSticks(arr):
    cnt = {}
    ans = []
    for i in arr:
        print(i)
        if i not in cnt:
            cnt[i] = 1
        else:
            cnt[i] += 1
    cur_sum = sum(cnt.values())
    while cnt:
        cur_min = min(cnt.keys())
        ans.append(cur_sum)
        cur_sum -= cnt[cur_min]
        del cnt[cur_min]
    return ans

時間複雜度:

建 table: O(n) + O(n) (find + insert)

加總: O(n)

min(): O(n)

後來寫完看討論，覺得最好的解答是:

def cutTheSticks(arr):
    ans = []
    while arr:
        ans.append(len(arr))
        arr = [x for x in arr if x != min(arr)]
    return ans

時間複雜度:

算長度: O(1)

min(): O(n)

insert(): O(n)

好像差蠻多的QQ