Divide and conquer (C++)


  • 0
    O
    class Solution {
    public:
        struct pos{
            pos(int _l, int _r) : l(_l), r(_r){}
            int l; int r;
        };
        pos rec(vector<int> & nums, int target, int start, int end) {
            if (end == start) {
                if (nums[start] == target) return pos(start, start);
                else return pos(-1, -1);
            }
            pos pos_l = rec(nums, target, start, (start+end)/2);
            pos pos_r = rec(nums, target, (start+end)/2+1, end);
            if (pos_l.r + 1 == pos_r.l) return pos(pos_l.l, pos_r.r);
            else {
                if (pos_l.l == -1) return pos_r;
                else return pos_l;
            }
        }
        vector<int> searchRange(vector<int>& nums, int target) {
            int n = nums.size();
            if (n == 0) return vector<int>(2, -1);
            pos pos_rsl = rec(nums, target, 0, n-1);
            vector<int> rsl;
            rsl.push_back(pos_rsl.l);
            rsl.push_back(pos_rsl.r);
            return rsl;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.