讨论/《画解剑指 Offer》 - 剑指 Offer 53 - I. 在排序数组中查找数字 I/
《画解剑指 Offer》 - 剑指 Offer 53 - I. 在排序数组中查找数字 I
共 3 个回复

忧伤的码畜

class Solution {
    public int search(int[] nums, int target) {
        int len = nums.length;
        int times = 0;
        if(len == 0){
            return times;
        }
        if(nums[0] > target || nums[len-1] < target){
            return times;
        }
        if(len < 64){
            for(int i:nums){
                if(i == target){
                    times++;
                }
            }
            return times;
        }
        int l = 0;
        int r = len-1;
        int cur = l + (r-l)/2;
        while(nums[cur] != target && cur!=r && cur!=l){
            if(nums[cur] > target){
                r = cur;
                cur = l+(r-l)/2;
            }else if(nums[cur] == target){
                break;
            }else{
                l = cur;
                cur = l+(r-l)/2;
            }
        }
    
        if(nums[cur] == target){
            times++;
            l = 1;
            r = 1;
            while(cur-l >= 0 && nums[cur-l] == target){
                times++;
                l++;
            }
            while(cur+r < nums.length && nums[cur+r] == target){
                times++;
                r++;
            }
        }
        return times;
    }
}
var singleNumber = function(nums,target) {
    let index = 0;

    if(!nums.includes(target)) return index; 

    for (let i = 0, len = nums.length; i < len; i++) {

        if(nums[i] === target) {
            index ++ 
        }

    }

    return index
};
class Solution {
    public int search(int[] nums, int target) {
    	int len = nums.length;
    	if(len == 0)
    		return 0;
    	
    	int firstPosition = findFirstPosition(nums, target);
    	if(firstPosition == -1)
    		return 0;
    	int lastPosition = findLastPosition(nums, target);
    	return lastPosition - firstPosition + 1;
    }
    private int findFirstPosition(int[] nums, int target) {
    	int left = 0;
    	int right = nums.length - 1;
    	while(left < right) {
    		int mid = left + (right - left) / 2;
    		if(nums[mid] < target) {
    			left = mid + 1;
    		}
    		else {
    			right = mid;
    		}
    	}
    	if(nums[left] == target)
    		return left;
    	return -1;
    }
    private int findLastPosition(int[] nums, int target) {
    	int left = 0;
    	int right = nums.length - 1;
    	while(left < right) {
    		int mid = left + (right - left + 1) / 2;
    		if(nums[mid] > target)
    			right = mid - 1;
    		else
    			left = mid;
    	}
    	return left;
    }
}