Total Occurrence of Target(Ladder)

Description

Given a target number and an integer array sorted in ascending order. Find the total number of occurrences of target in the array.

Example:
Given [1, 3, 3, 4, 5] and target = 3, return 2. Given [2, 2, 3, 4, 6] and target = 4, return 1. Given [1, 2, 3, 4, 5] and target = 6, return 0.

Challenge: Time complexity in O(logn)

Link

Lintcode-Ladder

Method

1. Binary Search
2. x

Example

1. 1

   class Solution {
   public:
    /**
     * @param A an integer array sorted in ascending order
     * @param target an integer
     * @return an integer
     */
    int totalOccurrence(vector<int>& nums, int target) {
        // Write your code here
        if (nums.empty()) {
            return 0;
        }
        int target_head = -2;
        int target_tail = -1;
        // find the start pos
        int start = 0;
        int end = nums.size()-1;
        while (start+1 < end) {
            int mid = start + (end-start)/2;
            if (target <= nums[mid]) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (target == nums[start]) {
            target_head = start;
        } else if (target == nums[end]) {
            target_head = end;
        }
        // fidn the end pos
        // start no change
        end = nums.size() -1;
        while (start+1 <end) {
            int mid = start + (end-start)/2;
            if (target >= nums[mid]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (target == nums[end]) {
            target_tail = end;
        } else if (target == nums[start]) {
            target_tail = start;
        }
        if (target_head == target_tail) {
            return 1;
        } else if (target_head >= 0 && target_tail >= 0) {
            return abs(target_head - target_tail) +1;
        } else {
            return 0;
        }
    }
   };
   

Similar problems

x

Tags

x