求最小数

Question

我想找一个列表中最小的数字。列表中的数字可能是

   1. decrease first and then increase (won't decrease again)
           [5,3,2,0,1,6,99]

   2. or increase only
           [3,4,5,6,7,8]

   3. or decrease only
           [8,6,4,3,2]

这些数字大于或等于0

我唯一能用的就是把当前号码和它的上一个号码以及下一个号码进行比较。但是太慢了。有没有O(logN)甚至更快的方法？

Answer 1

根据问题约束，只要比较序列中的两个元素的开始或结束，就可以在O(1)的时间复杂度中找到增加或减少序列的case-2和case-3。

现在，对于第一个具有先减后增属性的情况，可以用O(logN)时间复杂度找到，其中N是序列的长度。

如果我们分析一下，序列将看起来像下面。

\           /
 \         /
 (x)     (y)
   \     /
    \   /
    (ans) 

所以，在进行二元搜索时，每一步我们都会把搜索范围分成两半，然后根据元素的位置移动到其中一半。x 我们可以向右移动，如果中间元素存在于第二个递增部分，如 y 我们可以向左侧移动。这样一来，我们就会向答案的近似点移动。ans.

由于在每一步中，我们都是将搜索范围除以一半，然后向一半移动，所以解的复杂度变为O(logN)。

c++中的示例代码如下。

int findSmallest(vector<int>ar) {
   int n = ar.size();
   if (n == 1) return ar[0];
   if (ar[1] > ar[0]) return ar[0]; //Increase only condition
   if (ar[n - 1] < ar[n - 2]) return ar[n - 1]; // Decrease only condition
   int lo = 1, hi = n - 2;
   int ans;
   while (lo <= hi) {
      int mid = (lo + hi) / 2;
      if ((ar[mid] < ar[mid - 1]) && (ar[mid] < ar[mid + 1])) {
        ans = ar[mid];
        break;
      }
      if ((ar[mid] < ar[mid - 1]) && (ar[mid] > ar[mid + 1])) { //have to move right
         lo = mid + 1;
      } else {
        hi = mid - 1;
      }
   }
   return ans;
}

Answer 2

复杂度为对数的二分法的变体仍然有效。

• 测试前两个数字。如果它们在增加，你就完成了。
• 测试最后两个数字。如果它们在减少，你就完成了。
• 否则，范围的左边是递减斜率，右边是递增斜率。双分割，选择具有相同属性的一半。继续下去，直到范围折叠为1个元素。