[白俊/python/ソート]13週目の解答(#2751,#1427,#1026,#1764,#11004)

まず教材から学ぶソート
1.整列選択(Selection sort)
時間複雑度O(N^2)
2.ソートの挿入
時間複雑度O(N^2)
ただし、最良の場合(リストがほとんどソートされている場合)O(N)
3.クイックソート
O(NlogN)
しかし最悪の場合(ほぼ全て整列)O(N^2)
4.ソート数
O(N+K)
データのサイズ範囲が限られており、整数で表すことができる場合にのみ使用できます.
通常、最大データと最小データの差が1000000を超えない場合に有効です.
空間複雑度O(N+K)
5.Python既存ソートライブラリ
sorted()
クイックソートと同様のマージソートに基づいています.
最悪の場合はO(Nlogn)を保証する
演算回数?時間.
常にアルゴリズムを解く過程で、目がぼやけているのはデータの個数(ex.1≦N≦1000000.)であり、期間限定です.
今まで、私がコードを作って、できるだけ演算回数を減らせばいいのではないでしょうか.このような考えで、よく理解しようとは思わなかった.
しかし、ソートの場合、私はすでに定型化されたアルゴリズムを学習し、使用する方法であり、データの数、範囲、制限時間に応じて適切なソート方法を選択する必要があります.
時間とデータの数がもたらす最小時間の複雑さを理解するプロセスが必要だと思います.
(現在のメモリ制限は、目がぼやけているのが最大の努力です)
タイムアウト
Pythonは,1秒あたり2000万回の演算が可能であると考えられる.
ある問題の時間制限が2秒、100万個だと思ったら
4000万回の演算で100万個の並べ替え方法を見つけるのが正しい.
では,この問題はO(Nlogn)内で解決しなければならない.
(でもサーバーによって時間が違う…?)
問題ではまず時間制限(実行時間要件)を決定する必要があります.
時間が1秒に制限されているという問題に遭遇した場合、通常の基準は以下の通りです.

Nの範囲は500:時間複雑度O(N)³)問題を解決できるinアルゴリズムを設計した

Nの範囲は2000:時間複雑度O(N)²)問題を解決できるinアルゴリズムを設計した

Nの範囲が100000である場合、設計時間の複雑度がO(Nlogn)のアルゴリズムは問題

を解決することができる.

Nの範囲が1000000である場合:時間的複雑度O(N)のアルゴリズムを設計すれば、問題

を解決することができる.
🔗 ブログ1参照 / ブログ2参照
#2751ソート2
🔗 https://www.acmicpc.net/problem/2751
インプリメンテーション
時間制限:2秒、100万ソート->O(NlogN)
とても簡単なソート問題です!
まず,教材から学習したソート方法には何の可能性もないようだ(クイックソートは最悪の場合に発見される).
Pythonの既存のシステム並べ替え法を用いて解いた.
コード1(Python 3)

import sys

n=int(sys.stdin.readline().rstrip())
numList=[int(sys.stdin.readline().rstrip()) for _ in range(n)]

numList=sorted(numList)

for num in numList:
    print(num)

でもこのまま解けばいいの?これは役に立ちますか?...そこで,Pythonの既存のソート方法に対する集計ソート(Merge sort)を用いて解いた.🔗 コメントブログ
Python 3はタイムアウトします.既存のソート関数は本当によくできていたのか...感じました.
コード2(PyPy 3のみ成功、merge sort使用)

def merge_sort(numList):
    if len(numList)<=1:
        return numList
    
    mid = len(numList)//2
    left = numList[:mid]
    right = numList[mid:]
    
    left1=merge_sort(left)
    right1=merge_sort(right)
    
    return merge(left1,right1)

def merge(left, right):
    i=0
    j=0
    numList=[]
    
    while(i<len(left)) & (j<len(right)):
        if left[i] < right[j]:
            numList.append(left[i])
            i+=1
        else:
            numList.append(right[j])
            j+=1
    while (i<len(left)):
        numList.append(left[i])
        i+=1
    while (j<len(right)):
        numList.append(right[j])
        j+=1
    return numList

import sys

n=int(sys.stdin.readline().rstrip())
numList=[int(sys.stdin.readline().rstrip()) for _ in range(n)]

numList=merge_sort(numList)

for num in numList:
    print(num)

#1427内部
🔗 https://www.acmicpc.net/problem/1427
インプリメンテーション
制限時間:2秒、10個の数字を降順に並べ、0～9の範囲
これは完全に係数ソートで解決できる問題です!!
コード#コード#

import sys

digit=[0 for _ in range(10)]
number=sys.stdin.readline().rstrip()

for num in number:
    digit[int(num)]+=1

for i in range(9,-1,-1):
    if digit[i]==0:
        continue
    else:
        for j in range(digit[i]):
            print(i,end='')

#1026宝物
🔗 https://www.acmicpc.net/problem/1026
インプリメンテーション
教材の例題に似た問題!
a昇順に並べ替え、b降順に並べ替えた後
a bを順番に乗じると、最高価格が得られます.
コード#コード#

import sys
n=int(sys.stdin.readline().rstrip())
a=list(map(int,sys.stdin.readline().split()))
b=list(map(int,sys.stdin.readline().split()))
answer=0

a=sorted(a)
b=sorted(b,reverse=True)

for i in range(n):
    answer+=a[i]*b[i]
    
print(answer)

#1764ヒアリング雑誌
🔗 https://www.acmicpc.net/problem/1764
インプリメンテーション
聞いたことのない人の名前と見たことのない人の名前の中で同じものを探します.
set資料型で交差を求める.
ソートを利用して解く方法があるかどうか考えてみましょう...あきらめる.
コード#コード#

import sys

n1,n2=map(int,sys.stdin.readline().split())
canthear=set([sys.stdin.readline().rstrip() for _ in range(n1)])
cantsee=set([sys.stdin.readline().rstrip() for _ in range(n2)])
answer=[]

answer=sorted(canthear&cantsee)

print(len(answer))
for a in answer:
    print(a)

#11004 K番号
🔗 https://www.acmicpc.net/problem/11004
インプリメンテーション
制限時間:2秒500万の数字を並べ替える->このO(Nlogn)もだめ...より良いソート方法を実施すべきだ......
私はただ舞台poro merge sortと既存のソート方法をPyPy 3に回しただけで、タイムアウトはありませんが.
ちょっと気分が悪い...
コード1(PyPy 3)

import sys

n,k=map(int,sys.stdin.readline().split())
numList=list(map(int,sys.stdin.readline().split()))

numList=sorted(numList)

print(numList[k-1])

コード2(PyPy 3)

def merge_sort(numList):
    if len(numList)<=1:
        return numList
    
    mid = len(numList)//2
    left = numList[:mid]
    right = numList[mid:]
    
    left1=merge_sort(left)
    right1=merge_sort(right)
    
    return merge(left1,right1)

def merge(left, right):
    i=0
    j=0
    numList=[]
    
    while(i<len(left)) & (j<len(right)):
        if left[i] < right[j]:
            numList.append(left[i])
            i+=1
        else:
            numList.append(right[j])
            j+=1
    while (i<len(left)):
        numList.append(left[i])
        i+=1
    while (j<len(right)):
        numList.append(right[j])
        j+=1
    return numList

import sys

n,k=map(int,sys.stdin.readline().split())
numList=list(map(int,sys.stdin.readline().split()))

numList=merge_sort(numList)

print(numList[k-1])