[offer-37] Number number of occurrences in sorted array in 20190902/01

The number of times a number appears in a sorted array

  • Test Points: Arrays
  • Time limit: 1 second
  • Space limitation: 32768K
  • Statistics the number of times a number appears in a sorted array.
Ideas:

Seeing order, it must be a dichotomy search. The idea of this problem is to find the position of the first K and the last K minus each other and get the number of numbers.

The time complexity of the violent solution is O(n), and there are better solutions. The time complexity is O(logn):

1. Find the subscripts that appear for the first time. Let left, mid and right represent the beginning, middle and end of the array respectively.

If the number a[mid] in the middle of the array is greater than k, then right = mid-1;

If the number a[mid] in the middle of the array is less than k, then left = mid+1;

If the number a[mid] in the middle of the array is equal to k, judge whether a[mid-1] is equal to k, if not, it means that the subscript is the first appearing subscript and returns the mid subscript; if it is equal, it means that the first appearing subscript is still on the left side of mid, right = mid-1;

Repeat the above process recursively.

2. Find out the final subscript, the principle is the same as above.

Code:
public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if (array.length == 0) {
            return 0;
        }
        
        int firstK = getFirstK(array, k, 0, array.length - 1);
        int lastK = getLastK(array, k, 0, array.length - 1);
        if (firstK != -1 && lastK != -1) {
            return lastK - firstK + 1;
        }
        return 0;
    }
    public int getFirstK(int[] array, int k, int left, int right) {
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        if (array[mid] > k) {
            return getFirstK(array, k, left, mid - 1);
        } else if (array[mid] < k) {
            return getFirstK(array, k, mid + 1, right);
        } else if (mid - 1 >= 0 && array[mid - 1] == k) {
            return getFirstK(array, k, left, mid - 1);
        } else {
            return mid;
        }
    }
    
     public int getLastK(int[] array, int k, int left, int right) {
         int mid = (left + right) / 2;
         while (left <= right) {
             if (array[mid] > k) {
                 right = mid - 1;
             } else if (array[mid] < k) {
                 left = mid + 1;
             } else if (mid + 1 < array.length && array[mid + 1] == k) {
                 left = mid + 1;
             } else {
                 return mid;
             }
             mid = (left + right) / 2;
         }
         return -1;
     }
}
My question:

I'm still not familiar with the algorithm. It is not considered that if K is equal, mid cannot be returned directly. To make a judgment, if it comes to the previous k, then we need to compare with the previous number, whether the former number is equal to k, and if so, it means that the previous number may be equal, and we need to continue to iterate.
Similarly, for loops, it is necessary to compare whether the latter number equals k, and if so, to show that this is not the last k, and to move index backwards for comparison.

Other ideas 1:

Violence solving method, with O(n) time complexity, needs to traverse the entire array.

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == k) {
                count++;
            }
        }
        return count;
    }
}
Other ideas 2:

Because data is all integers, you can change it slightly, not to search for the two positions of k, but to search for k-0.5 and k+0.5.
These two numbers should be inserted in the position, and then subtract.

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
       return biSearch(array, k + 0.5) - biSearch(array, k - 0.5);
    }
    public int biSearch(int[] array, double k) {
        int start = 0, end = array.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (array[mid] > k) {
                end = mid - 1;
            } else if (array[mid] < k) {
                start = mid + 1;
            }
        }
        return start;
    }
}

Tags: less

Posted on Mon, 02 Sep 2019 01:55:32 -0700 by Hardwarez