【剑指offer-Java版】38数字在排序数组中出现的次数

淩亂°似流年 2022-08-21 09:48 53阅读 0赞

数字在排序数组中出现的次数：  
最简单粗暴的方法是O(n^2)

可能的解法可以采用二分，首先根据二分找到给定数字在数组中的位置，然后再左右二分，找到边界（第一个和最后一个），左右边界的差值就是出现次数

public class _Q38<T> {
    
        public int GetNumberOfK(int nums[], int k){
            if(nums == null) return 0;
    
            int first = GetFirstK(nums, k, 0, nums.length - 1);
            int last = GetLastK(nums, k, 0, nums.length - 1);
    
            int result = 0;
            if(first > -1 && last > -1){
                result = last - first + 1;
            }
    
            return result;
        }
    
        private int GetFirstK(int nums[], int k, int start, int end){
            if(nums == null || start > end) return -1;
    
            int mid = (start + end) / 2;
            if(nums[mid] == k){
                if(mid == 0) return mid;
                if(mid > 0 && nums[mid - 1] != k) return mid;
                return GetFirstK(nums, k, start, mid - 1); // 容易遗漏的逻辑分支
            }else if(nums[mid] > k){
                return GetFirstK(nums, k, start, mid - 1);
            }else if(nums[mid] < k){
                return GetFirstK(nums, k, mid + 1, end);
            }
    
            return -1;
        }
    
        private int GetLastK(int nums[], int k, int start, int end) {
            if (nums == null || start > end) return -1;
    
            int mid = (start + end) / 2;
            if (nums[mid] == k) {
                if (mid == end) return mid;
                if (mid < end && nums[mid + 1] != k) return mid;
                return GetLastK(nums, k, mid + 1, end); // 容易遗漏的逻辑分支
            } else if (nums[mid] > k) {
                return GetLastK(nums, k, start, mid - 1);
            } else if (nums[mid] < k) {
                return GetLastK(nums, k, mid + 1, end);
            }
    
            return -1;
        }
    
        }

测试代码：

public class _Q38Test extends TestCase {
        
    
        _Q38 numOfK = new _Q38();
    
        public void test(){
    
            int nums1[] = {
       1, 2, 3, 3, 3, 3, 4, 5};
            int k1 = 3;
            int k2 = 6;
            int k3 = 4;
    
            int result = 0; 
            result = numOfK.GetNumberOfK(nums1, k1);
            System.out.println(result);
            result = numOfK.GetNumberOfK(nums1, k2);
            System.out.println(result);
            result = numOfK.GetNumberOfK(nums1, k3);
            System.out.println(result);
            result = numOfK.GetNumberOfK(null, k3);
            System.out.println(result);
    
    
        }
        }