配列内の逆シーケンス対python
牛客ネット上の剣指offerプログラミング問題
タイトル:
配列内の2つの数値で、前の1つの数値が後の数値より大きい場合、この2つの数値は逆シーケンスペアを構成します.1つの配列を入力し,この配列における逆順対の総数Pを求める.P対1000000007型取りの結果を出力します.出力P%1 000000007
バブル思想
この問題を見て、まず思いついたのはバブルソート法、つまり2つの比較であり、時間の複雑度は(n^2)であり、ここではバブルソートを一定の改善を行う:ある比較過程で、2つの要素の交換位置がなければ、すでにソートされていることを説明し、サイクルを終了する.
しかし時間が複雑すぎて通れない...
思想を統合する.
集計ソートの原理を根絶すると,時間複雑度O(n*logn)の方法,すなわち集計ソート法に基づいてコードを1行追加することができる:cout=+len(left)-l
それからやはり通じなくて、他の言語の集計バージョンはできて、pythonが対象を受け取ったような気がします.の
最後にネット上でもっと簡潔な方法を見ました.は、元のシーケンスをソートしてから、シーケンスが完了した配列から最小のものを取り出します.元の配列の位置は、元の配列よりも大きい数がその前にあることを示します.元の配列から要素を削除するたびに、後に取り出した要素が元の配列の中で最小であることを保証します.これにより、その位置は、その前にある数、すなわち逆シーケンス対数を表すことができます.
タイトル:
配列内の2つの数値で、前の1つの数値が後の数値より大きい場合、この2つの数値は逆シーケンスペアを構成します.1つの配列を入力し,この配列における逆順対の総数Pを求める.P対1000000007型取りの結果を出力します.出力P%1 000000007
バブル思想
この問題を見て、まず思いついたのはバブルソート法、つまり2つの比較であり、時間の複雑度は(n^2)であり、ここではバブルソートを一定の改善を行う:ある比較過程で、2つの要素の交換位置がなければ、すでにソートされていることを説明し、サイクルを終了する.
def test(array):
t=0
for i in range(len(array)-1,0,-1):
flag=False
for j in range(i):
if array[j]>array[j+1]:
array[j],array[j+1]=array[j+1],array[j]
t+=1
flag=True
if not flag:
break
return t%(2*(10**5))
しかし時間が複雑すぎて通れない...
思想を統合する.
集計ソートの原理を根絶すると,時間複雑度O(n*logn)の方法,すなわち集計ソート法に基づいてコードを1行追加することができる:cout=+len(left)-l
class Solution:
def InversePairs(self, data):
# , , O(n^2)。 , O(nlogn)
global count
count=0
def A(array):
global count
if len(array)<=1:
return array
k=int(len(array)/2)
left=A(array[:k])
right=A(array[k:])
l=0
r=0
result=[]
while land rif left[l]1
else:
result.append(right[r])
r+=1
count+=len(left)-l
result+=left[l:]
result+=right[r:]
return result
A(data)
return count%1000000007
それからやはり通じなくて、他の言語の集計バージョンはできて、pythonが対象を受け取ったような気がします.の
最後にネット上でもっと簡潔な方法を見ました.
class Solution:
def InversePairs(self, data):
count = 0
copy = []
for i in data:
copy.append(i)
copy.sort()
for i in range(len(copy)):
count += data.index(copy[i])
data.remove(copy[i])
return count%1000000007
a=[1,2,3,4,5,6,7,0]
Solution().InversePairs(a)