0

私は Interiewstreet の Insertion sort challenge Link を Python でチャレンジ用にプログラムしようとしましたが、これが私のコードです。

プログラムは、入力要素の制限 (よくわかりません) に対しては正常に実行されますが、より大きなサイズの入力に対しては誤った出力を返します。誰が私が間違っているのか教えてもらえますか?

# This program tries to identify number of times swapping is done to sort the input array 

"""
=>Get input values and print them
=>Get number of test cases and get inputs for those test cases
=>Complete Insertion sort routine
=>Add a variable to count the swapping's 
"""

def sort_swap_times(nums):
  """ This function takes a list of elements and then returns the number of times 
      swapping was necessary to complete the sorting
  """

  times_swapped = 0L
  # perform the insertion sort routine
  for j in range(1, len(nums)):
    key = nums[j]
    i = j - 1
    while i >= 0 and nums[i] > key:
      # perform swap and update the tracker
      nums[i + 1] = nums[i]
      times_swapped += 1
      i = i - 1
    # place the key value in the position identified
    nums[i + 1] = key

  return times_swapped


# get the upper limit.
limit = int(raw_input())  
swap_count = []

# get the length and elements.
for i in range(limit):
  length = int(raw_input())
  elements_str = raw_input() # returns a list of strings

  # convert the given elements from str to int
  elements_int = map(int, elements_str.split())

  # pass integer elements list to perform the sorting
  # get the number of times swapping was needed and append the return value to swap_count list
  swap_count.append(sort_swap_times(elements_int))


# print the swap counts for each input array
for x in swap_count:
  print x
4

1 に答える 1

2

あなたのアルゴリズムは正しいですが、これは問題に対する素朴なアプローチであり、大規模なテスト ケース (つまり、len(nums) > 10000) では Time Limit Exceed シグナルが発生します。アルゴリズムの実行時の複雑さを分析してみましょう。

for j in range(1, len(nums)):
    key = nums[j]
    i = j - 1
    while i >= 0 and nums[i] > key:
      # perform swap and update the tracker
      nums[i + 1] = nums[i]
      times_swapped += 1
      i = i - 1
    # place the key value in the position identified
    nums[i + 1] = key

上記のスニペットで必要なステップ数は、1 + 2 + .. + len(nums)-1 または len(nums)*(len(nums)-1)/2 ステップに比例します。つまり、O(len(数値)^2)。

ヒント:

すべての値が [1,10^6] 以内になるという事実を利用します。ここで実際に行っているのは、リスト内の反転の数を見つけることです。つまり、i < j st nums[i] > nums[j] のすべてのペアを見つけます。対数時間の複雑さで各挿入操作に必要なスワップの数を見つけることができるデータ構造を考えてみてください。もちろん、他のアプローチもあります。

スポイラー:

バイナリ インデックス ツリー

于 2013-01-13T03:29:59.533 に答える