码疯窝

LeetCode 每日一题 — Search for a Range

2015/02/03 10:09:04    分类: 日志连载    0人评论 次浏览

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

算法分析: 此题规定时间复杂必须为O(logn)就此首先想得到的就二分法. 设定start和end, 递归查找target, 然后来更新start 跟 end 的值.

Java:

public class Solution {
    int start = -1;
    int end = -1;
    public int[] searchRange(int[] A, int target) {
        this.loop(A, target, 0, A.length - 1);
        int[] rst = {this.start, this.end};
        return rst;
    }
    protected void loop(int[] A, int target, int left, int right) {
        if (left > right)
            return;
        int mid = left + (right - left) / 2;
        if (target == A[mid]) {
            if (this.start == -1 || this.start > mid)
                this.start = mid;
            if (this.end == -1 || this.end < mid)
                this.end = mid;
            this.loop(A, target, left, mid - 1);
            this.loop(A, target, mid + 1, right);
        } else if (target < A[mid])
            this.loop(A, target, left, mid - 1);
        else if (target > A[mid])
            this.loop(A, target, mid + 1, right);
    }
}

C++:

class Solution {
public:
    int start = -1;
    int end = -1;
    
    vector searchRange(int A[], int n, int target) {
        loop(A, target, 0, n - 1);
        vector rst;  
        rst.push_back(start);  
        rst.push_back(end);  
        return rst;
    }
    void loop(int A[], int target, int left, int right) {
        if (left > right) return;
        int mid = left + (right - left) / 2;
        if (target == A[mid]) {
            if (start == -1 || start > mid)
                start = mid;
            if (end == -1 || end < mid)
                end = mid;
            loop(A, target, left, mid - 1);
            loop(A, target, mid + 1, right);
        } else if (target < A[mid]) 
            loop(A, target, left, mid - 1);
        else if (target > A[mid])
            loop(A, target, mid + 1, right);
    }
};

Python:

class Solution:
    start = -1
    end = -1
    def searchRange(self, A, target):
        self.loop(A, target, 0, len(A) -1)
        return [self.start, self.end]
    
    def loop(self, A, target, left, right):
        if (left > right):
            return
        mid = left + (right - left) / 2
        if (target == A[mid]):
            if (self.start == -1 or self.start > mid):
                self.start = mid
            if (self.end == -1 or self.end < mid):
                self.end = mid
            self.loop(A, target, left, mid - 1)
            self.loop(A, target, mid + 1, right)
        if (target < A[mid]):
            self.loop(A, target, left, mid - 1)
        elif (target > A[mid]):
            self.loop(A, target, mid + 1, right)
        
继续查看有关 日志连载的文章

0个访客评论