數字在升序陣列中出現的次數
描述
給定一個長度為 n 的非降序陣列和一個非負數整數 k ，要求統計 k 在陣列中出現的次數
決議
排序陣列的查找問題首先考慮二分法
使用二分法找到左右邊界的位置，然后長度一減即可
解題思路：
排序陣列的查找問題首先考慮使用 二分法 解決，其可將 遍歷法 的 線性級別 時間復雜度降低至 對數級別
演算法流程：
1、初始化： 宣告 i, j 雙指標分別指向 array 陣列左右兩端
2、回圈二分： 設 m = (i + j) / 2 為每次二分的中點（ "/" 代表向下取整除法，因此恒有 i≤m1、當 array[m] > array[j] 時： m 一定在 左排序陣列 中，即旋轉點 x 一定在 [m + 1, j] 閉區間內，因此執行 i = m + 1
2、當 array[m] < array[j] 時： m 一定在 右排序陣列 中，即旋轉點 x 一定在[i, m]閉區間內，因此執行 j = m
3、當 array[m] = array[j] 時： 無法判斷 mm 在哪個排序陣列中，即無法判斷旋轉點 x 在 [i, m] 還是 [m + 1, j] 區間中，解決方案： 執行 j = j - 1 縮小判斷范圍
3、回傳值： 當 i = j 時跳出二分回圈，并回傳 旋轉點的值 array[i] 即可，
代碼
package esay.JZ53數字在升序陣列中出現的次數;
public class Solution {
private int bisearch(int[] array, double k) {
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = (right + left) / 2;
if (array[mid] > k) {
right = mid - 1;
} else if (array[mid] < k) {
left = mid + 1;
}
}
return left;
}
public int GetNumberOfK(int[] array, int k) {
return bisearch(array, k+0.5) - bisearch(array, k - 0.5);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/531380.html
標籤：Java
上一篇：如何在回圈中命令Ajax呼叫