#LeetCode:34. Find First and Last Position of Element in Sorted Array

C++ 的話,利用函式庫內建的 lower_boundupper_bound 即可得解。如果要知道詳細的做法可以參考 C++ reference – lower_boundC++ reference – upper_bound ,基本上就是在二分搜尋的時候對等號的情況給予不一樣的行為即可。

C++(8ms)

/************************************************************************/
/* LeetCode 34. Find First and Last Position of Element in Sorted Array */
/* Author: Maplewing [at] knightzone.studio                             */
/* Version: 2019/03/31                                                  */
/************************************************************************/
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
  vector<int> searchRange(vector<int>& nums, int target) {
    auto lowerPosition = lower_bound(nums.begin(), nums.end(), target);
    if(lowerPosition == nums.end() || 
      *lowerPosition != target)
      return vector<int>(2, -1);

    auto upperPosition = upper_bound(nums.begin(), nums.end(), target);
    return vector<int> { 
      (int)(lowerPosition - nums.begin()), 
      (int)(upperPosition - nums.begin() - 1) 
    };
  }
};

回應

目前無留言,歡迎留言!

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料

%d 位部落客按了讚: