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 = nums.size();
    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(nums.begin() + 1, nums.end(), nums[0], greater<int>{});
    return it == nums.end() ? nums[0] : *it;
  }
};

• 不使用 STL 的解法

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