Index of first occurrence


  • 0
    P

    Given an array, [1,1,1,1,4,4,4,6,6,6,6,8,8] and an integer z. Return the index of the first occurrence of z in the given array.
    Follow-up: Can you improve run-time if input is sorted?

    Example: For the above array, if z=6, return 7 i.e. the index of the first occurrence of 6 in the array.


  • 0
    K

    binary search if array is sorted. if you find z, then just iterate in the negative direction to find the first occurrence.


  • 0
    H
    public static void main(String[] args) {
    	
    	int [] nums = {1,1,1,1,4,4,4,6,6,6,6,8,8};
    	int target = 10;
    	
    	int index = binSearch (0, nums.length-1, nums, target);
    	if (index == -1) {
    		System.out.println("null");
    		return ;
    	} else {
    		for (int i = index; i >= 0 ; i --) {
    			if (nums[i] != target) {
    				System.out.println(i+1);
    				return ;
    			}
    		}
    	}
    	
    }
    
    public static int binSearch (int pre, int end, int [] nums, int target) {
    	
    	while (pre < end && pre <= nums.length-1 && end >=0) {
    		int mid = (pre + end) / 2;
    		if (nums[mid] < target) {
    			pre = mid + 1;
    		} else if (nums[mid] > target) {
    			end = mid - 1;
    		} else {
    			return mid;
    		}
    	}
    	return -1;
    }
    

Log in to reply
 

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