劍指Offer--第一彈：算法之搜索算法（一）-創(chuàng)新互聯(lián)

JZ53 數(shù)字在升序數(shù)組中出現(xiàn)的次數(shù) 描述：

給定一個(gè)長度為 n 的非降序數(shù)組和一個(gè)非負(fù)數(shù)整數(shù) k ，要求統(tǒng)計(jì) k 在數(shù)組中出現(xiàn)的次數(shù)
數(shù)據(jù)范圍：1000 ≤ n ≤ 1000, 0 ≤ k ≤ 100，數(shù)組中每個(gè)元素的值滿足 0 ≤ val ≤ 100
要求：空間復(fù)雜度 O(1)，時(shí)間復(fù)雜度 O(logn)

解析：

題干中的非降序數(shù)組指升序數(shù)組 -->即為有序數(shù)組
既然為有序數(shù)組，那就方便我們?nèi)?duì)它做一些操作了。

方法思路： 方法一：暴力法

思路：
	直接對(duì)數(shù)組進(jìn)行遍歷，有一個(gè)符合條件的非負(fù)整數(shù)就對(duì)定義的計(jì)數(shù)參數(shù)加一
	直到遍歷完畢后，返回計(jì)數(shù)參數(shù)即可。
時(shí)間復(fù)雜度：O(n) -- 一次遍歷循環(huán)
空間復(fù)雜度：O(1)

• Java相關(guān)代碼：

  public int getNumberOfK01(int[] array, int k) {int sum = 0;
      for (int each : array) {if (each == k) {sum++;
          }
      }
      return sum;
  }

方法二：二分法

分治思想：
	分治即“分而治之”
	“分”指的是將一個(gè)大而復(fù)雜的問題劃分成多個(gè)性質(zhì)相同但是規(guī)模更小的子問題，子問題繼續(xù)按照這樣劃分，直到問題可以被輕易解決；
	“治”指的是將子問題單獨(dú)進(jìn)行處理。
	經(jīng)過分治后的子問題，需要將解進(jìn)行合并才能得到原問題的解，因此整個(gè)分治過程經(jīng)常用遞歸來實(shí)現(xiàn)
思路：
	二分查找可以降低時(shí)間復(fù)雜度，從而提高代碼執(zhí)行效率。
	利用二分查找結(jié)合分治思想將查詢的值加減0.5，從而使得查詢的值兩次左邊界得以確定，兩次左邊界確定后進(jìn)行加減即可得到查詢值出現(xiàn)在數(shù)組中的次數(shù)。
時(shí)間復(fù)雜度：O(log2n)
空間復(fù)雜度：O(1)

• Java相關(guān)代碼：

  public int getNumberOfK02(int[] array, int k) {return binarySearch(array, k + 0.5) - binarySearch(array, k - 0.5);
  }
  
  private int binarySearch(int[] arr, double number) {// 左邊界
      int left = 0;
      // 右邊界
      int right = arr.length - 1;
      // 中間值下標(biāo)
      int mid;
      while (left<= right) {// 使用無符號(hào)右移可以有效避免正整數(shù)溢出問題
          mid = (left + right) >>>1;
  
          if (arr[mid]< number) {// 更新左邊界
              left = mid + 1;
          }
  
          if (arr[mid] >number) {// 更新右邊界
              right = mid - 1;
          }
      }
      return left;
  }

個(gè)人學(xué)習(xí)后的總結(jié)，如有不足之處，請(qǐng)及時(shí)指正，謝謝。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站建設(shè)哪家好，找成都創(chuàng)新互聯(lián)公司！專注于網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、微信小程序、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了大同免費(fèi)建站歡迎大家使用！
文章題目：劍指Offer--第一彈：算法之搜索算法（一）-創(chuàng)新互聯(lián)
瀏覽路徑：http://m.jiaotiyi.com/article/diodji.html