编程之战 第二百四一章 排序的方法
作者:程序小猿的小说      更新:2019-05-23

  因为列表本身是无序的。

  杨成很快萌生出一种想法:

  如果把它变成有序的,会不会更好处理呢?

  所以第一步,对列表由小到大进行排序。

  那个缺失的编号,要么在有序列表的最前面,要么在中间某个位置,要么在最后面。

  所以,接下来,从1遍历到100,和列表元素做比对。

  1,2,3...100

  1,3,4...100

  看到没,第一个不相等的数字,就是缺失的编号。

  在这个例子里面是2。

  这个方法,比之前的方法效率更高。

  因为排序的缘故,它是N乘以logN的时间复杂度。

  那有没有复杂度更低的方法呢?