LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 参考 #33，考虑左侧升序与右侧升序

class Solution {
 public:
  int findMin(vector<int>& nums) {
    int l = 0;
    int r = size(nums);
    while (l < r) {
      int m = l + (r - l) / 2;
      if (nums[m] >= nums[l]) {       // 左侧升序
        if (nums[l] > nums[r - 1]) {  // 位于右侧
          l = m + 1;
        } else {  // 位于左侧
          return nums[l];
        }
      } else {  // 左侧不为升序则右侧一定为升序
        if (m > 0 && nums[m] > nums[m - 1]) {  // 位于左侧
          r = m;
        } else {  // 位于右侧
          return nums[m];
        }
      }
    }
    return INT_MAX;
  }
};

• 二分查找第一个比首元素小的数，如果未找到则首元素就是最小元素

class Solution {
 public:
  int findMin(vector<int>& nums) {
    auto it = upper_bound(begin(nums) + 1, end(nums), nums[0], greater<int>{});
    return it == end(nums) ? nums[0] : *it;
  }
};

• 不使用 STL 的解法

class Solution {
 public:
  int findMin(vector<int>& nums) {
    int l = 1;
    int r = size(nums);
    while (l < r) {
      int m = l + (r - l) / 2;
      if (nums[m] < nums[0]) {
        r = m;
      } else {
        l = m + 1;
      }
    }
    return l != size(nums) ? nums[l] : nums[0];
  }
};