一次二分查找先找到大概位置,然后遍历
数字在排序数组中出现的次数
http://www.nowcoder.com/questionTerminal/70610bf967994b22bb1c26f9ae901fa2
1.用hashmap
2.二分查找,先找到k所在的大致位置,然后转化位两个数组正向和逆向遍历,获得k值所在数组中的次数。
import java.util.Arrays; public class Solution { public int GetNumberOfK(int [] array , int k) { int low = 0; int high = array.length; int pos= -1; while(low<high) { int middle = low+(high-low)/2; if(array[middle]==k) {//[low, middle k ,high] pos=middle; break; }else if(array[middle]<k){ low =middle+1; }else if(array[middle]>k){//[low, k middle ,high] high=middle-1; } } int count = 0; if(pos==-1) {//说明数组中没有该数字 return 0; } //分为两个数组;[0,pos),[pos,array.length) int[] newArr1 = Arrays.copyOfRange(array, 0 , pos); //[2 3 k][ k k 1 2 3 ] int[] newArr2 = Arrays.copyOfRange(array, pos,array.length); for(int i=newArr1.length-1;i>=0;i--) {//倒着遍历 if(newArr1[i]!=k) { break; } count++; } for(int j=0;j<=newArr2.length-1;j++) {//正着遍历 if(newArr2[j]!=k) { break; } count++; } return count; } }