美文网首页
【不熟练】知识迁移能力-数字在排序数组中出现的次数

【不熟练】知识迁移能力-数字在排序数组中出现的次数

作者: Jacinth | 来源:发表于2017-07-20 01:28 被阅读0次

    数字在排序数组中出现的次数

    题目描述

    统计一个数字在排序数组中出现的次数。

    public class Solution {
        /*解题思路:
        有序数组的问题,采用二分查找。找到第一个K和最后一个K,两者的位置相减
        */
        public int GetNumberOfK(int [] array , int k) {
            int length=array.length;
            if(length==0){
                return 0;
            }
            int firstK=getFirstK(array,k,0,length-1);
            int lastK=getLastK(array,k,0,length-1);
            if(firstK!=-1&&lastK!=-1){
                return lastK-firstK+1;
            }
            return 0;
        }
        //递归写法
        private int getFirstK(int [] array , int k, int start, int end){
            if(start > end){
                return -1;
            }
            int mid = (start + end) >> 1;
            if(array[mid] > k){
                return getFirstK(array, k, start, mid-1);
            }else if (array[mid] < k){
                return getFirstK(array, k, mid+1, end);
            }else if(mid-1 >=0 && array[mid-1] == k){//重点array[mid-1] == k
                return getFirstK(array, k, start, mid-1);
            }else{
                return mid;
            }
        }
        //循环写法
        private int getLastK(int [] array , int k, int start, int end){
            int length = array.length;
            int mid = (start + end) >> 1;
            while(start <= end){
                if(array[mid] > k){
                    end = mid-1;
                }else if(array[mid] < k){
                    start = mid+1;
                }else if(mid+1 < length && array[mid+1] == k){//重点array[mid+1] == k
                    start = mid+1;
                }else{
                    return mid;
                }
                mid = (start + end) >> 1;
            }
            return -1;
        }
    }
    

    相关文章

      网友评论

          本文标题:【不熟练】知识迁移能力-数字在排序数组中出现的次数

          本文链接:https://www.haomeiwen.com/subject/ylarkxtx.html