Index of first occurrence


  • 1
    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.


  • 1
    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;
    }
    

  • 0

    @hao-zhang This will be linear in the case you have O(n) elements of the target element


Log in to reply
 

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