Q題目

在排序數(shù)組中，找出給定數(shù)字的出現(xiàn)次數(shù)，比如 [1, 2, 2, 2, 3] 中2的出現(xiàn)次數(shù)是3次。

---

Answer解法

這道題要求出結(jié)果不難，但要求最有解的話，就需要花費(fèi)一番功夫了。常見解法有如下四種：

定義： 要查詢的數(shù)字為key 查詢的數(shù)組為arr

1）暴力窮舉

直接從頭遍歷計(jì)數(shù)就可以了

2）遍歷開始和最后一次出現(xiàn)的index

• 從前開始遍歷，遇到與key相同，則停止遍歷，得到startIndex

• 從后開始遍歷，遇到與key相同，則停止遍歷，得到endIndex

• 數(shù)字出現(xiàn)次數(shù)為：endIndex-startIndex

該做法比方法一好一些，減少了一部分計(jì)算次數(shù)

---

方法一和方法二代碼如下：

package 微軟面試題數(shù)字次數(shù);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("方法一測(cè)試：不存在key--"+getNumTimes(arr, 11));System.out.println("方法一測(cè)試：存在一個(gè)key--"+getNumTimes(arr, 3));System.out.println("方法一測(cè)試：存多個(gè)key--"+getNumTimes(arr, 9));System.out.println();System.out.println("方法二測(cè)試：不存在key--"+getNumTimes2(arr, 11));System.out.println("方法二測(cè)試：存在一個(gè)key--"+getNumTimes2(arr, 3));System.out.println("方法二測(cè)試：存多個(gè)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;}//方法二：遍歷出開頭和結(jié)尾public static int getNumTimes2(int[] arr,int key){int count=0;//key出現(xiàn)的次數(shù)int start=-1;//key第一次出現(xiàn)的位置--索引有index=0，所以這里用-1int end=-1;//key最后一次出現(xiàn)的位置//超出arr的最大值和最小值就沒必要遍歷了if(key>=arr[0]&&key<=arr[arr.length-1]){//計(jì)算startfor (int i = 0; i < arr.length; i++) {if(arr[i]==key){start=i;break;}}}//計(jì)算end--若start為最后一個(gè)元素或key(即start=-1）不存在時(shí)，沒必要求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;}}

運(yùn)行結(jié)果：

---

3）二分法查找所有數(shù)字

直接使用二分法去查找所有出現(xiàn)的值，相對(duì)于前兩種計(jì)算次數(shù)少一些

代碼如下：

package 微軟面試題數(shù)字次數(shù);public class Test2 {//方法三：二分法查找//參數(shù)：arr--查找的數(shù)組 key--要查找的數(shù)字 // startIndex和endIndex為在數(shù)組arr中的查找范圍--startIndex:起始下標(biāo) endIndex:截止下標(biāo)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;//輸入的參數(shù)不合法}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("方法三測(cè)試：存在多個(gè)key--"+count);}}

注意：count為static變量，所以測(cè)試時(shí)，只能分別測(cè)試三種情況

---

4）二分法查找和for循環(huán)結(jié)合

• 使用二分法查找數(shù)字，查詢到第一個(gè)key后馬上結(jié)束

• 根據(jù)key的下標(biāo)向前和向后遍歷，直到與key不相同為止，獲得count

與前三種方法相比，大大減少了計(jì)算的次數(shù)，不過這還不是最佳算法

代碼如下：

package 微軟面試題數(shù)字次數(shù);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("方法三測(cè)試：不存在key--"+getNumTimes3(arr, 11));System.out.println("方法三測(cè)試：存在一個(gè)key--"+getNumTimes3(arr, 3));System.out.println("方法三測(cè)試：存多個(gè)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]){//判斷有沒有keyint 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;}}

運(yùn)行結(jié)果如下：

---

5）二分法查找開始和結(jié)束index

使用二分法查詢開始和結(jié)束的index，關(guān)鍵是邊界問題的判斷。

開始邊界：與前一個(gè)數(shù)字比較，若不相同則是邊界

結(jié)束邊界：與后一個(gè)數(shù)字比較，若不相同則是邊界

與方法四相比，大多數(shù)情況下，該方法更計(jì)算次數(shù)更少，在少部分情況下，方法是更好。但總體上方法5更好。

代碼如下：

package 微軟面試題數(shù)字次數(shù);public class Test3 {public static void main(String[] args) {int[] arr={1,3,7,7,7,7,8,9,9,10};System.out.println("方法五測(cè)試：不存在key--"+GetNumberOfK(arr, 11));System.out.println("方法五測(cè)試：存在一個(gè)key--"+GetNumberOfK(arr, 3));System.out.println("方法五測(cè)試：存多個(gè)key--"+GetNumberOfK(arr, 9));}// （1）GetFirstK：找到數(shù)組中第一個(gè)k的下標(biāo)。如果數(shù)組中不存在k，返回-1public 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：找到數(shù)組中最后一個(gè)k的下標(biāo)。如果數(shù)組中不存在k，返回-1public 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：找到數(shù)組中第一個(gè)和最后一個(gè)k的下標(biāo)進(jìn)行減法運(yùn)算得到最終結(jié)果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;}}

測(cè)試結(jié)果：

總結(jié)

以上是生活随笔為你收集整理的算法--微软面试：指定数字在数组中出现的次数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。