查找字符数组中出现次数最多的字符

plus2047 发布于2019-08-16 18:05 / 1394人阅读

摘要：给定一个字符数组，例如找出数组中出现次数最多的字符，如果存在相同次数的字符，取出现较早者。

给定一个字符数组，例如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;
        }
    }

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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