アルゴリズム:O(n)複雑度のアルゴリズムを設計し,大量数の中で上位10個の最大数を見つけた.
41829 ワード
目次:1.O(n)複雑度のアルゴリズム を設計する1、質問:カウントソート 2、原理 2.大量の数の中で上位10個の最大数 を見つけた.1、問題 2、挿入法による解決構想(時間複雑度:O(kn)) 3、ヒープソートを用いた解決構想(時間複雑度:O(nlog(k)) 4、pythonが持参したheapqモジュールを使用して、上位10要素 を見つけます.三.その他 1、問題 2、リストにおいて2つの数が見つかったものと、与えられた数に等しいもの(見つかった下付き文字を返す) 3、新しいリストは現在のリストの下付き文字を格納し、現在のリストの値は新しい下付き文字の番号 とする.
一.O(n)複雑度のアルゴリズムを設計する
1、質問:カウント順には現在、リストの数範囲が0から100の間であり、リストの長さは約100万であり、設計アルゴリズムはO(n)時間の複雑さの中でリストを 並べ替える.
2、原理これらの数の中で最大の数が何であるかを知る必要があります. は次に、最大数に等しい長さのリスト を生成する.ループliリストのすべての数、liに現れるたびにこの数は生成されたcountリストに を加算する.これによりcountリストにおける対応する位置にリストliにおける全数の出現回数 を記録することができる.それからループcountで、この数が何回現れるかliリストに順番にいくつか書くと、次の効果 が現れます.
答え:
二.大量数の中で上位10個の最大数を見つける
1、問題現在n個数(n>10000)があり、アルゴリズムを設計し、大きさ順に前世の大きな数を得る. アプリケーションシーン:ランキングTOP 10 2、挿入法による解決構想(時間複雑度:O(kn))は、ソート対象リストの最初の11要素を先に取り出し、挿入ソートを使用して を先に整列する.そして順番に並べ替えられていない数を循環し、TOP 10リストの11番目の要素を1つずつ置換し、もう一度並べ替え を挿入する.このように1回のリストを循環するだけで前11の大きい要素が得られ、最後にリストがスライスし、前10の大きい要素を切り出すことができる である.
挿入による解決:
3、スタック並べ替えによる解決構想(時間複雑度:O(nlog(k)))リストの最初の10の要素を取って1つの小さい根の山を創立して、山の頂上は現在の10の大きい数(小さい根の山を創立します) ですは、元のリストを順次後方に巡回する、リスト内の要素については、スタックトップより小さい場合は無視し、スタックトップより大きい場合は、スタックトップをその要素に交換し、スタックを順次調整する .リストのすべての要素を巡回した後、逆順序でスタックトップ をポップアップする
ヒープソートの解決:
スタックの上位10要素:
4、pythonが持っているheapqモジュールを使ってトップ10の要素を見つける
heapqモジュールの解決:
三.その他
1、問題重複数のある昇順リストで指定数の下付き範囲 が見つかる.は、例える、リスト[1,2,3,4,5]であり、3を検索すると(2,4)1を検索すると(0,0) を返す.
答え:
2、リストに2つの数の和が与えられた数に等しいものを見つける(見つけた下付き文字を返す)
答え:
3、新しいリストは現在のリストの下付き文字を保存し、現在のリストの値は新しい下付き文字の番号とする
1.原理例えば現在リストli 1=[2,1,4]があり、この方法を使用するとli 1の中で最大の数がどれだけあるか(例えば、ここで最大の数は:6) を知る必要がある.リストの初期値li 2=[None,None,None,None,None,None] を新規作成 forループを使用してli 1を巡り、li 1[0]の2を初めて取り、li 2にli 2[2]=0 を設定するで2回目に取ったのは1がli 2[1]=0 であった.で3回目に取ったのは4がli 2[4]=0 であった.最後に得られたli 2=[None,0,0,None,0] 2.上記の原理に従って、リストに2つの数の和が与えられた数に等しいものを見つけることができます(見つかった下付きを返します)注意:この方法では、現在のリストの最大値を知る必要があります.
答え:
一.O(n)複雑度のアルゴリズムを設計する
1、質問:カウント順
2、原理
答え:
def count_sort(li, max_num):
count = [0 for i in range(max_num + 1)]
for num in li:
count[num] += 1
i = 0
print('count',count)
for num,m in enumerate(count): # count， li
for j in range(m): # li
li[i] = num
i += 1
li = [3,4,5,3,2,4,5,6,7,4]
count_sort(li,10)
print(li) #[2, 3, 3, 4, 4, 4, 5, 5, 6, 7]
二.大量数の中で上位10個の最大数を見つける
1、問題
挿入による解決:
#
def insert(li,i):
tmp = li[i] # tmp
j = i - 1 # li[j]
while j >= 0 and li[j] < tmp:
#li[j] < tmp 10
li[j + 1] = li[j] #
j = j - 1
li[j + 1] = tmp # tmp ，
def insert_sort(li):
for i in range(1, len(li)):
insert(li, i)
def topk(li,k):
top = li[0:k+1]
insert_sort(top) # 11
for i in range(k+1, len(li)): #
top[k] = li[i] # top
insert(top, k) # top
return top[:-1]
li = list(range(10000))
import random
random.shuffle(li)
a = topk(li,10)
print(a)
3、スタック並べ替えによる解決構想(時間複雑度:O(nlog(k)))
ヒープソートの解決:
import random
def sift(data, low, high):
''' ：
:param data:
:param low:
:param high:
:return:
'''
i = low #i
j = 2 * i+ 1 #j
tmp = data[i] #tmp （ ）
while j <= high: # （ ） #
if j + 1 <= high and data[j] > data[j + 1]: # ，
j += 1
if tmp > data[j]: # tmp ，
data[i] = data[j] #
i = j # （ ）
j = 2 * i + 1 # （ j<=high ， ）
else:
break #
data[i] = tmp #
def topn(li,n):
heap = li[0:n] # 10
for i in range(n//2 -1, -1, -1): # 10
sift(heap, i, n-1)
#
for i in range(n, len(li)): #
if li[i] > heap[0]: #
heap[0] = li[i] #
sift(heap, 0, n-1) #
for i in range(n - 1, -1, -1): # for ，
heap[0], heap[i] = heap[i], heap[0]
sift(heap, 0, i-1)
return heap
li = list(range(1000))
import random
random.shuffle(li)
a = topn(li,10)
print(a) #[999, 998, 997, 996, 995, 994, 993, 992, 991, 990]
スタックの上位10要素:
# !/usr/bin/env python
# -*- coding:utf-8 -*-
import random
def sift(data, low, high):
''' :
:param data:
:param low:
:param high:
:return:
'''
i = low # i
j = 2 * i + 1 # j
tmp = data[i] # tmp （ ）
while j <= high: # （ ）
if j + 1 <= high and data[j] > data[j + 1]: # ，
j += 1
if tmp > data[j]: # tmp ，
data[i] = data[j] #
i = j # （ ）
j = 2 * i + 1 # （ j<=high ， ）
else:
break #
data[i] = tmp #
def topn(li, n):
# 1、 10
heap = li[0:n] # 10
for i in range(n // 2 - 1, -1, -1): # 10
sift(heap, i, n - 1)
# 2、 li 10 heap
for i in range(n, len(li)): #
if li[i] > heap[0]: #
heap[0] = li[i] #
sift(heap, 0, n - 1) #
# 3、
for i in range(n - 1, -1, -1): # for ，
heap[0], heap[i] = heap[i], heap[0]
sift(heap, 0, i - 1)
return heap
li = list(range(1000))
import random
random.shuffle(li)
print topn(li, 10) # [999, 998, 997, 996, 995, 994, 993, 992, 991, 990]
4、pythonが持っているheapqモジュールを使ってトップ10の要素を見つける
heapqモジュールの解決:
import heapq
import random
heap = []
data = list(range(1000))
random.shuffle(data)
print(heapq.nlargest(10,data))
# [999, 998, 997, 996, 995, 994, 993, 992, 991, 990]
三.その他
1、問題
答え:
l = list(range(1,101))
def bin_search(data_set,val):
low = 0
high = len(data_set) - 1
while low <= high:
mid = (low+high)//2
if data_set[mid] == val:
left = mid
right = mid
while left >=0 and data_set[left] == val:
left -= 1
while right < len(data_set) and data_set[right] == val:
right += 1
return (left+1,right-1)
elif data_set[mid] < val:
low = mid + 1
else:
high = mid - 1
return
n = bin_search(l,2)
print(n) # 1 ： (1, 1)
2、リストに2つの数の和が与えられた数に等しいものを見つける(見つけた下付き文字を返す)
答え:
import copy
li = [1,2,4,3,5,]
target = 5
def bin_search(data_set,val,low,high):
while low <= high:
mid = (low+high)//2
if data_set[mid] == val:
return mid
elif data_set[mid] < val:
low = mid + 1
else:
high = mid - 1
return
def func2():
li2 = copy.deepcopy(li)
li2.sort()
for i in range(len(li2)):
a = i
b = bin_search(li2, target - li2[a], i+1, len(li2)-1)
if b:
return (li.index(li2[a]),li.index(li2[b]))
print(func2()) # (0, 2)
3、新しいリストは現在のリストの下付き文字を保存し、現在のリストの値は新しい下付き文字の番号とする
1.原理
答え:
import copy
li = [1,2,4,3,5,]
target = 3
max_num = 10
def func():
a = [None for i in range(max_num+1)] # a， li ， None
for i in range(len(li)):
a[li[i]] = i
if a[target-li[i]] != None:
return (a[li[i]], a[target-li[i]])
print(func())