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

题目描述

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

分析

因为有序,所以二分查找。先用二分查找找到该数字的位置,再从该位置分别往左往右计算两边跟他相等的个数。最后相加。

代码:

public class Solution {
public int GetNumberOfK(int [] array , int k) {
int index = binaryFindK(array, 0, array.length - 1, k);
if (index == -1) return 0;
int ind = index;
int leftCount, rightCount;
leftCount = rightCount = 0;
while ((index - 1) >= 0 && array[--index] == k)
leftCount++;
while ((ind + 1) < array.length && array[++ind] == k)
rightCount++;
return 1 + leftCount + rightCount;
}
public int binaryFindK(int [] array, int low, int high, int k) {
if (low <= high) {
int mid = low + (high-low) / 2;
if (array[mid] == k) return mid;
else if (array[mid] < k) binaryFindK(array, mid+1, high, k);
else binaryFindK(array, low, mid-1, k);
}
return -1;
}
}

欢迎关注公众号: FullStackPlan 获取更多干货

Copyright © 2016 - 2017 LBD's Blog All Rights Reserved.

访客数 : | 访问量 :