Find the count of occurences of a specific integer in a sorted integer array


  • 0
    B

    The C# code below is just to give an idea for the Log(n) solution. I have not compiled or run it for errors. The benefit here is that if the median is the target, it will not take N operations if there are less than N occurences of the target. This is accomplished by scanning from center to left and right.

    Enjoy!

    public int CountFreq(int [] nums, int target) {
        return countFreq(nums, target, 0, nums.Length);
    }
        public int countFreq(int [] nums, int target, int low, int hi){
    
            if ((hi-low) == 0) return 0;
            
            int mid = (hi-low) / 2;
            int count = 0;
            
            if (nums[mid] == target){
                // scan and return
                for (int i = mid; i < hi; i++){
                    if (nums[i] == target){
                        count++; 
                    }
                    else {
                        break;
                    }
                }
                for (int i = mid-1; i >= 0; i--) {
                    if (nums[i] == target){
                        count++;
                    }
                    else {
                        break;
                    }
                }     
                      
                return count;
            }
            if (nums[mid] < target){
                return countFreq(nums, target, mid,size-1);
            }
            else {
                return countFreq(nums, target,0,mid-1);
            }
        }

  • 0

    This is a variation of LeetCode's Search for a Range problem, binary search is the way to go.


Log in to reply
 

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