查找字符數組中出現次數最多的字符

plus2047 發布于2019-08-16 18:05 / 1412人閱讀

摘要：給定一個字符數組，例如找出數組中出現次數最多的字符，如果存在相同次數的字符，取出現較早者。

給定一個字符數組，例如char[] chars = { "a", "b", "b", "b", "b", "c", "a", "a", "a"};
找出數組中出現次數最多的字符，如果存在相同次數的字符，取出現較早者。
一個問題的解決方案有多種：

利用數據結構的特性，鏈表保證了插入順序，Map正是我們想要的字符與出現次數對應關系的映射，代碼如下，只需遍歷一次

    char[] chars = {"a", "b", "b", "b", "b", "c", "a", "a", "a"};
    Map countMap = new LinkedHashMap<>();
    Map indexMap = new LinkedHashMap<>();
    int length = chars.length;
    // 目標字符
    char target = 0;
    // 出現的最多次數
    int maxCount = 0;
    for (int index = 0; index < length; index++) {
        char aChar = chars[index];
        Integer value = countMap.get(aChar);
        
        if (value == null) {
            // 如果已經存在某字符 maxCount 比數組剩余待遍歷元素數量還多，沒必要考慮它了
            if (maxCount > length - (index + 1)) {
                break;
            }
            countMap.put(aChar, 1);
            indexMap.put(aChar, index);
            
        } else {
            countMap.put(aChar, value += 1);
            
            if (maxCount == value) {
                // 出現相同次數的 char，取先在數組中出現的
                // 即誰出現的次數 + 出現的 index 小
                // 也可以將 value 封裝成含有索引和次數的對象，那樣只需聲明一個 map
                if (indexMap.get(aChar) < indexMap.get(target)) {
                    target = aChar;
                }
            } else if (maxCount < value) {
                maxCount = value;
                target = aChar;
            }
        }        
    }

將原數組拷貝成orderedChars然后排序，接著遍歷查找orderedChars和originalChars，操作比較麻煩，不推薦，但是可以鍛煉純數組操作和“指針”的使用

    char[] originalChars = {"a", "a", "c", "b", "b", "b", "c", "b", "c", "c", "a", "d", "d", "d"};
    int length = originalChars.length;
    // 拷貝原數組，并排序
    char[] orderedChars = new char[length];
    System.arraycopy(originalChars, 0, orderedChars, 0, length);
    Arrays.sort(orderedChars);
    // 最大次數 尋找的字符，給個默認值
    int maxCount = 1;
    char target = orderedChars[0];
    int headIndex = 0, tailIndex = 1, targetIndex = -1;
    for (; tailIndex < length; ) {
        // 移動 tailIndex 的時候 headIndex 不動
        // tailIndex++ == (length - 1) 特殊處理 orderedChars 最后幾位都是同一 char 的情況
        if (orderedChars[headIndex] != orderedChars[tailIndex] || (tailIndex++ == (length - 1))) {
            // 臨時計數器
            int tmpCount = tailIndex - headIndex;
            if (tmpCount < maxCount) {
                // 已找到出現次數最多的char 即 headIndex 的上一個
                target = orderedChars[headIndex - 1];
                break;
                
            } else if (tmpCount > maxCount) {
                maxCount = tmpCount;
                target = orderedChars[headIndex];

            } else {
                // 如果遇到相同次數的就比較麻煩了
                // 需要在原數組中比較誰先出現，即索引更小者
                int tmpCurIndex = -1;
                for (int i = 0; i < length; i++) {
                    if (originalChars[i] == target && targetIndex == -1) {
                        targetIndex = i;
                    } else if (originalChars[i] == orderedChars[headIndex] && tmpCurIndex == -1) {
                        tmpCurIndex = i;
                    }
                    if (tmpCurIndex != -1 && targetIndex != -1) {
                        if (tmpCurIndex < targetIndex) {
                            targetIndex = tmpCurIndex;
                            target = originalChars[targetIndex];
                        }
                        break;
                    }
                }
            }

            // 在往后找的過程中，如果找到滿足條件的就將 headIndex 移至tailIndex，即 headIndex = tailIndex
            // tailIndex 繼續移動，即 ++ 操作
            headIndex = tailIndex;
        }
    }

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/74941.html

面試題：尋找一個字符串中出現次數最多的字符以及出現的次數

摘要：要求編寫代碼實現尋找一個字符串中出現次數最多的字符以及出現的次數。最后只需要在集合中找到值最大的即可。要求編寫代碼實現：尋找一個字符串中出現次數最多的字符以及出現的次數。解法一：用刪除法實現 (挺巧妙的一種) public class FindTheMostAppearChar { public static void main(String[] args) { del...

lei___ 2019-08-19 11:46 評論0 收藏0
找出數組中出現次數最多的一項并統計次數

摘要：擴展字符串中出現次數最對的字符是哪一項并統計實例方法可返回指定位置的字符。請注意，并沒有一種有別于字符串類型的字符數據類型，所以返回的字符是長度為的字符串。語法注釋字符串中第一個字符的下標是。如果參數不在與之間，該方法將返回一個空字符串。實例1 var a,sum = 0; var obj = {}; var arr = [1,3,7,3,1,8,1,10,6,1]; for(va...

eechen 2019-08-20 18:57 評論0 收藏0
三道關于字符串的JavaScript面試題解析

摘要：方法二生成統計次數字符最多的是，出現了次點評稍微好一點。問題三題目如何給字符串加千分符例如方法一轉換的方法轉化為數組最終的結果點評將字符串轉化為數組，然后對其切分重組。分享幾道js面試題，自己感覺還是挺重要的，當看到題目的時候希望大家先花幾秒鐘考慮一下，然后在看答案。如果有比較好的解法，歡迎大家留言指正，謝謝大家！第一題題目：寫一個字符串轉換成駝峰的方法？例如：borde...

Sourcelink 2019-08-22 15:41 評論0 收藏0
JavaScript初應用：找到數組中出現最多的字母并給出個數以及每一個所在的位置

摘要：剛剛接觸一周的時間，熟悉了最基本的知識，這是自己面對的第一個的邏輯性的代碼題目，自己嘗試了寫了，結果還算可以，因為有好多知識涉及到了后面的知識，就有點吃力了。以下代碼總結于網上前輩給出的參考答案和結合了自己的理解和注釋，請多多指正。剛剛接觸JS一周的時間，熟悉了最基本的js知識，這是自己面對的第一個js的邏輯性的代碼題目，自己嘗試了寫了，結果還算可以，因為有好多知識涉及到了后面的do...

Zhuxy 2019-08-01 15:34 評論0 收藏0
JavaScript初應用：找到數組中出現最多的字母并給出個數以及每一個所在的位置

摘要：剛剛接觸一周的時間，熟悉了最基本的知識，這是自己面對的第一個的邏輯性的代碼題目，自己嘗試了寫了，結果還算可以，因為有好多知識涉及到了后面的知識，就有點吃力了。以下代碼總結于網上前輩給出的參考答案和結合了自己的理解和注釋，請多多指正。剛剛接觸JS一周的時間，熟悉了最基本的js知識，這是自己面對的第一個js的邏輯性的代碼題目，自己嘗試了寫了，結果還算可以，因為有好多知識涉及到了后面的do...

darkerXi 2019-08-22 10:36 評論0 收藏0