使用二進制搜索查找字串中出現頻率最高的字符

假設給定一個長度字串，n并且有 26 個 ASCII 字符可以構成該字串。相同的字符在字串中組合在一起（例如 aaabbbcccddd）。找出出現頻率最高的字符。

蠻力是掃描整個字串并迭代計算字符數，這需要 O(n) 時間和 O(1) 空間。是否有 O(log n) 解決方案？我得到了二進制搜索的提示，以查找包含最常見字符的磁區，但我不確定二進制搜索如何幫助我消除字串的一半。

uj5u.com熱心網友回復：

隨著您的字符被分組，問題被簡化為找到最長的后續字母序列......

所以是的，您可以使用二進制搜索來查找每個序列的大小，即序列O(m.log(n))的m<=n數量（不同的字母）。正如您所說m<=26，您可以將其視為不斷導致O(log(n))

演算法將是這樣的：

1. 考慮你的字串是char s[n];和結果int l=0;

2. for (i=0;i<n;)

3. 二分查找j位置

   最后一個字符的哪里s[i]==s[j]哪里i <= j < n

4. 記住最大值l=max(l , j 1-i)

5. i=j 1

6. continue來自 #2 的回圈

但是請注意，任何字母只能有一個序列，因此類似的字串abaaaaaa將不起作用。

uj5u.com熱心網友回復：

您可以使用二進制搜索在字串的子范圍內查找字符的最后一次出現（或最右邊的出現）來解決此問題。

您可以使用它在輸入字串中跳躍，從一個字符到另一個字符，無論同一個字符重復的頻率如何。當你跳躍時，你會記住迄今為止最頻繁出現的字符以及重復的頻率。

middle( left : Integer, right : integer) : (mid : Integer, valid : Boolean)

1. 讓 mid = left floor(right - left, 2)
2. 回傳（中，左！=中）

find-rightmost(s : String, c : Char, left : Integer, right : Integer) : (lastIndex : Integer, found : Boolean)

1. 如果 left >= right 然后回傳 (left, false) ;; 空范圍案例
2. 如果 s[right] = c 然后回傳 (right, true) ;; 跨越整個范圍的情況
3. 讓（中間，有效）=中間（左，右）;; 如果 left = middle 則 mid 無效
4. 如果有效 AND s[mid] = c 然后 find-rightmost(s, c, mid, right)
   else 如果有效則 find-rightmost(s, c, left, mid)
   else return (left, s[left] = c)

find-rightmost是遞回形式的經典二進制搜索。

most-frequent-char(s : String) : (c : Char, frequency : Integer)?

1. 讓 n = 長度（s）
2. 讓 nm1 = n - 1
3. 如果 n = 0 則回傳 nil ;; 或 nullptr 的 NULL 或其他任何您喜歡的值，
   如果 n = 1 然后回傳 (s[0], 1) ;; 長度為 1 的普通字串
   else
   let mutable i = 0
   let mutable maxf = 0
   let mutable cmax = '-'
   while i < nm1
   let (ilast, found) = find-rightmost(s, s[i], i 1, nm1 )
   ~~~ 更新 max, cmax 合適時
   如果找到 then
   i := ilast 1
   else
   i := i 1
   end while
   return (cmax,maxf)

這產生了大約 O(m*log(n)) 的總復雜度，其中 m 是不相交字符的數量。

由于偽代碼不容易被驗證為實際“作業”，因此在 Common Lisp 中也是如此：

(defparameter *test-cases*
  '(""
    "a"
    "ab"
    "aabcd"
    "aaaaaaaaaa"
    "abbbbbbbcccdd"))

(defun middle (left right)
  (let ((mid (  left (floor (- right left) 2))))
    (values mid (/= mid left))))

(defun find-rightmost (s c left right)
  (if (< left right)
      (multiple-value-bind (mid valid) (middle left right)
    (cond
      ((char-equal c (aref s right))
       (values right t))
      ((and valid (char-equal c (aref s mid)))
       (find-rightmost s c mid right))
      (valid
       (find-rightmost s c left mid))
      (t (values left (char-equal c (aref s left))))))
      (values left nil)))

(defun most-frequent-char (s)
  (let* ((n (length s))
     (n-1 (- n 1)))
    (cond
      ((= n 0)
       nil)
      ((= n 1)
       (list :char (aref s 0) :freq 1))
      (t ;; string length > 1 - we actually have to work...
       (loop
     with i = 0
     with cmaxf = nil
     with nmax = 0
     while (< i n-1)
     for c = (aref s i)
     do (multiple-value-bind (ilast found)
        (find-rightmost s c (  i 1) n-1)
          (if found
          (let ((freq (  1 (- ilast i))))
            (when (> freq nmax)
              (setf nmax freq)
              (setf cmaxf c))
            (setf i (  ilast 1)))
          (progn
            (when (= 0 nmax)
              (setf nmax 1)
              (setf cmaxf c))
            (incf i))))
     finally (return (list :char cmaxf :freq nmax)))))))
          
(defun run-tests ()
  (mapcar #'(lambda (in)
          (list in (most-frequent-char in)))
      *test-cases*))

CL-USER> (format t "~{~S~%~}~%" (run-tests))
("" NIL)
("a" (:CHAR #\a :FREQ 1))
("ab" (:CHAR #\a :FREQ 1))
("aabcd" (:CHAR #\a :FREQ 2))
("aaaaaaaaaa" (:CHAR #\a :FREQ 10))
("abbbbbbbcccdd" (:CHAR #\b :FREQ 7))

標籤：算法

上一篇：檢查非數字值是否在范圍內的最佳方法是什么？

下一篇：全域變數是否需要更長的獲取時間？