Q题目
在排序数组中，找出给定数字的出现次数，比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。
Answer解法
这道题要求出结果不难，但要求最有解的话，就需要花费一番功夫了。常见解法有如下四种：
定义： 要查询的数字为key 查询的数组为arr
1）暴力穷举
直接从头遍历计数就可以了
2）遍历开始和最后一次出现的index
从前开始遍历，遇到与key相同，则停止遍历，得到startIndex
从后开始遍历，遇到与key相同，则停止遍历，得到endIndex
数字出现次数为：endIndex-startIndex
该做法比方法一好一些，减少了一部分计算次数
方法一和方法二代码如下：
package 微软面试题数字次数;
import java.util.Arrays;
import java.util.HashSet;
public class Test1 {
public static void main(String[] args) {
int[] arr={1,3,7,7,7,7,8,9,9,10};
System.out.println("方法一测试：不存在key--"+getNumTimes(arr, 11));
System.out.println("方法一测试：存在一个key--"+getNumTimes(arr, 3));
System.out.println("方法一测试：存多个key--"+getNumTimes(arr, 9));
System.out.println();
System.out.println("方法二测试：不存在key--"+getNumTimes2(arr, 11));
System.out.println("方法二测试：存在一个key--"+getNumTimes2(arr, 3));
System.out.println("方法二测试：存多个key--"+getNumTimes2(arr, 9));
}
//方法一：暴力解法--完整遍历
public static int getNumTimes(int[] arr,int key){
int count=0;
//超出arr的最大值和最小值就没必要遍历了
if(key>=arr[0]&&key<=arr[arr.length-1]){
for (int i : arr) {
if(i==key){
count++;
}
}
}
return count;
}
//方法二：遍历出开头和结尾
public static int getNumTimes2(int[] arr,int key){
int count=0;//key出现的次数
int start=-1;//key第一次出现的位置--索引有index=0，所以这里用-1
int end=-1;//key最后一次出现的位置
//超出arr的最大值和最小值就没必要遍历了
if(key>=arr[0]&&key<=arr[arr.length-1]){
//计算start
for (int i = 0; i < arr.length; i++) {
if(arr[i]==key){
start=i;
break;
}
}
}
//计算end--若start为最后一个元素或key(即start=-1）不存在时，没必要求end了
if(start!=-1 && start<arr.length-1){
for(int i=arr.length-1;i>=0;i--){
if(arr[i]==key){
end=i;
break;
}
}
count=Math.abs(end-start+1);
}
return count;
}
}
运行结果：
3）二分法查找所有数字
直接使用二分法去查找所有出现的值，相对于前两种计算次数少一些
代码如下：
package 微软面试题数字次数;
public class Test2 {
//方法三：二分法查找
//参数：arr--查找的数组 key--要查找的数字
// startIndex和endIndex为在数组arr中的查找范围--startIndex:起始下标 endIndex:截止下标
static int count=0;
public static void getNumTimes4ByBinary(int[] arr, int key, int startIndex,int endIndex){
int middle=(startIndex+endIndex)/2;
if(startIndex>endIndex){
return;//输入的参数不合法
}
if(arr[middle]==key){
count++;
//向前找
getNumTimes4ByBinary(arr, key, startIndex, middle-1);
//向后找
getNumTimes4ByBinary(arr, key, middle+1, endIndex);
}else if (arr[middle]<key) {
getNumTimes4ByBinary(arr, key, middle+1, endIndex);
}else {
getNumTimes4ByBinary(arr, key, startIndex, middle-1);
}
}
public static void main(String[] args) {
int[] arr={1,3,7,7,7,7,8,9,9,10};
getNumTimes4ByBinary(arr, 7, 0 , arr.length-1);
System.out.println("方法三测试：存在多个key--"+count);
}
}
注意：count为static变量，所以测试时，只能分别测试三种情况
4）二分法查找和for循环结合
使用二分法查找数字，查询到第一个key后马上结束
根据key的下标向前和向后遍历，直到与key不相同为止，获得count
与前三种方法相比，大大减少了计算的次数，不过这还不是最佳算法
代码如下：
package 微软面试题数字次数;
import java.util.Arrays;
import java.util.HashSet;
public class Test1 {
public static void main(String[] args) {
int[] arr={1,3,7,7,7,7,8,9,9,10};
System.out.println();
System.out.println("方法三测试：不存在key--"+getNumTimes3(arr, 11));
System.out.println("方法三测试：存在一个key--"+getNumTimes3(arr, 3));
System.out.println("方法三测试：存多个key--"+getNumTimes3(arr, 9));
}
//方法三：二分法 --先二分法查找判断是否存在key，并获得索引
public static int getNumTimes3(int[] arr,int key){
int count=0;
//超出arr的最大值和最小值就没必要遍历了
if(key>=arr[0]&&key<=arr[arr.length-1]){
//判断有没有key
int index=Arrays.binarySearch(arr, key);
if(index>=0){
//存在key值
//向前找
for(int i=index;i>=0;i--){
if(arr[i]!=key){
break;
}
count++;
}
//向后找
for(int i=index+1;i<arr.length;i++){
if(arr[i]!=key){
break;
}
count++;
}
}
}
return count;
}
}
运行结果如下：
5）二分法查找开始和结束index
使用二分法查询开始和结束的index，关键是边界问题的判断。
开始边界：与前一个数字比较，若不相同则是边界
结束边界：与后一个数字比较，若不相同则是边界
与方法四相比，大多数情况下，该方法更计算次数更少，在少部分情况下，方法是更好。但总体上方法5更好。
代码如下：
package 微软面试题数字次数;
public class Test3 {
public static void main(String[] args) {
int[] arr={1,3,7,7,7,7,8,9,9,10};
System.out.println("方法五测试：不存在key--"+GetNumberOfK(arr, 11));
System.out.println("方法五测试：存在一个key--"+GetNumberOfK(arr, 3));
System.out.println("方法五测试：存多个key--"+GetNumberOfK(arr, 9));
}
// （1）GetFirstK：找到数组中第一个k的下标。如果数组中不存在k，返回-1
public static int GetFirstK(int[] data, int k, int start, int end) {
if (start > end) {
return -1;
}
int middIndex = (start + end) / 2;
int middData = data[middIndex];
if (middData == k) {
if ((middIndex > 0 && data[middIndex - 1] != k) || middIndex == 0) {
return middIndex;
} else {
end = middIndex - 1;
}
} else if (middData > k) {
end = middIndex - 1;
} else {
start = middIndex + 1;
}
return GetFirstK(data, k, start, end);
}
// （2）GetLastK：找到数组中最后一个k的下标。如果数组中不存在k，返回-1
public static int GetLastK(int[] data, int k, int start, int end) {
if (start > end) {
return -1;
}
int middIndex = (start + end) / 2;
int middData = data[middIndex];
if (middData == k) {
if ((middIndex < data.length - 1 && data[middIndex + 1] != k) || middIndex == end) {
return middIndex;
} else {
start = middIndex + 1;
}
} else if (middData > k) {
end = middIndex - 1;
} else {
start = middIndex + 1;
}
return GetLastK(data, k, start, end);
}
// (3)GetNumberOfK：找到数组中第一个和最后一个k的下标进行减法运算得到最终结果
public static int GetNumberOfK(int[] data, int k) {
int number = 0;
if (data != null && data.length > 0) {
int first = GetFirstK(data, k, 0, data.length - 1);
int last = GetLastK(data, k, 0, data.length - 1);
if (first > -1 && last > -1) {
number = last - first + 1;
}
}
return number;
}
}
测试结果：
