leetcode：範囲の検索（配列、バイナリ検索）

Leetcode Search Range Array

整数のソートされた配列が与えられた場合、与えられたターゲット値の開始位置と終了位置を見つけます。

アルゴリズムの実行時の複雑さは、次のオーダーである必要があります または （ログ n ）。

ターゲットが配列に見つからない場合は、[-1, -1]を返します。

例えば、
与えられた[5, 7, 7, 8, 8, 10]目標値8
[3, 4]を返します。

分析：質問の意味は、ターゲット値が指定された開始位置に順序付けられた配列で検出され、ターゲットが返されない場合は戻ります[1,1]。

アイデア：binarySearchLow（）を使用して、ターゲット値が最小のインデックス番号以上であることを確認し、binarySearchUp（）を使用して、ターゲット値が最大インデックス番号以下であることを確認します。次に、インデックス範囲を取得できます。

次のようにコーディングします。

class Solution { private: int binarySearchLow(vector& nums, int target, int begin, int end) { if(begin > end) return begin int mid = begin + (end - begin) / 2 if(nums[mid] end) return end int mid = begin + (end - begin) / 2 if(nums[mid] > target) return binarySearchUp(nums, target, begin, mid - 1) else return binarySearchUp(nums, target, mid + 1, end) } public: vector searchRange(vector& nums, int target) { vector res(2, -1) if(nums.empty()) return res int high = binarySearchUp(nums, target, 0, nums.size() -1) int low = binarySearchLow(nums, target, 0, nums.size() - 1) if(high >= low) { res[0] = low res[1] = high return res } return res } }

その他の方法：最初に、同じターゲット値を持つ順序付けられた数値の配列の位置を見つけて、数値を確認します。

コード：

class Solution { public: vector searchRange(vector& nums, int target) { int low=0 int high=nums.size()-1 vector ans(2,-1) int flag = -1 marker target value if there are the same number of array // int start,end while(low<=high){ int mid=(low+high)/2 if(nums[mid]target){ high=mid-1 } else{ flag=mid break } } if(flag!=-1){ start=flag while(start>=0 && nums[start]==target){ start-- } ans[0]=start+1 end=flag while(end

その他の解決策：問題を解決するためのショートコード（イテレーター）

class Solution { public: vector searchRange(vector& nums, int target) { vector ret vector::iterator start = find(nums.begin(), nums.end(), target) vector::reverse_iterator end = find(nums.rbegin(), nums.rend(), target) ret.push_back( (start == nums.end() ? -1 : start-nums.begin() ) ),ret.push_back(nums.size() - 1 - (end - nums.rbegin())) return ret } }

python：

class Solution(object): def searchRange(self, nums, target): ''' :type nums: List[int] :type target: int :rtype: List[int] ''' if target not in nums: return ([-1,-1]) low = nums.index(target) nums.sort(reverse=True) high = len(nums)-nums.index(target)-1 result = [] result.append(low) result.append(high) return (result)