0

我尝试为 Python 中的挑战编写 Interiewstreet 的插入排序挑战链接， 下面是我的代码。

该程序对于输入元素的限制（我不确定）运行良好，但对于较大尺寸的输入返回错误输出。谁能指导我我做错了什么？

# 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 回答