摘要
Title: 113. 特殊排序
Tag: 二分、交互题
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

113. 特殊排序

• 题意

  

• 思路

  题目的意思就是，你知道N个元素的大小关系，要求你通过$compare$函数来将N个元素排序

  思路就是从$2-N$的每个数，都在结果数组中进行二分，然后插入到适合的地方即可

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-02-22 11:38:52
  FilePath: \ACM\Acwing\113.py
  LastEditTime: 2022-02-22 11:49:35
  '''
  # Forward declaration of compare API.
  # def compare(a, b):
  # @param a, b int
  # @return bool
  # return bool means whether a is less than b.
  
  
  class Solution(object):
      def specialSort(self, N):
          """
          :type N: int
          :rtype: List[int]
          """
          a = [1]
          for i in range(2, N + 1):
              l, r = 0, len(a) - 1
              while l < r:
                  mid = l + r >> 1
                  if compare(i, a[mid]):
                      r = mid
                  else:
                      l = mid + 1
              if compare(i, a[r]):
                  a.insert(r, i)
              else:
                  a.insert(r + 1, i)
          return a