输入一段不减的整数，如11111223333，怎么快速计算重复次数最多的那个数

Question

输入
一段不减整数，如：11111223333
输出
出现次数最多的那个数字，如：本例中1的出现次数最多，输出1

输入的数字具有以下规律
1.数字为正整数，不一定从1开始
2.如果增长，则increment = 1
3.整数的总量不会超过1W，但是事先无法知道总共会输入多少整数

Answer 1

这题不用对所有数字计数，那样很慢。
如果增长，则increment = 1
把数字当作字符串来处理，只要找出所有增长的点的位置就可以了，然后把相邻的点的位置相减，即可得到长度。
因为不一定是从1开始，所有可能的增长的点为："12"，"23"，"34"，。。。"78"，"89"

例如：
将11111223333转为字符串，查找增长点
结果：12-位置4，23-位置6
增长点补正（加1）：12-位置5，23-位置7
初始位置补0，末尾补字符串长度len,得到
[0,5,7,11]
取相邻两点之差
[5,2,4]
所以，出现次数最多的是第一个元素，5次

---

以下为6/14日更新

@刀之魂 和 @tedBear 的想法很棒，比我原来的回答好多了。

受大家的启发，我来更新一个不需要遍历的算法：
由于increment = 1，所以看开头和结尾2个数，即可算出出现数字有几种
（如11111223333，开头为1，结尾为3，则出现的数为1到3，共3种）
那么，考虑出现N种数的情况
N=1就不用说了，等于白送答案。
先从简单的N=2说起吧，因为有些细节在N=2的情况说了，后面N>2的情况类似的细节就省略了。

N=2

2分采样
若len为奇数，取len/2处的数，这个数就是出现次数最多的数。
若len为偶数，len/2处是间隙，所以取该间隙前后2个数，这2个数相同的话，答案就是这个数，如果不同的话，答案是这两个数出现次数一样，并列最多。

N>2

N分采样，取0、len/N、2len/N、...、（N-1）len/N、len处的（N+1）个点，（由于间隙的情况太复杂，这里省略，请参考N=2的处理方法）
然后统计这（N+1）个点里面，出现次数最多的数，把出现次数最多的数叫做M1，出现第二多的叫做M2，依次类推
若 （M1的次数 - M2次数） 大于等于2，则答案为M1
若 （M1的次数 - M2次数） 小于2，那么
2N分采样(若2N>len,则len分采样)，取len/2N、3len/2N、5len/2N、。。。。、处的N个点，与前面N分法时候取的（N+1）个点组合，重新求M1，M2，。。。。
若 （M1的次数 - M2次数） 大于等于2，则答案为M1
若 （M1的次数 - M2次数） 小于2，
则4N分采样(若4N>len,则len分采样)
。。。。依次类推，8N，16N。。。。
直至找到 （M1的次数 - M2次数） 大于等于2为止。其中若变为len分采样，结束条件不需要（M1的次数 - M2次数）大于等于2，M1就是答案。

小结

这个算法大部分时候是比较快的，最差的情况是N个数的各个次数都相差很小，或者都相同，那就会进入最后的len分采样，等于遍历，那还不如一开始就直接遍历比较快。
但是数据的分布越是不均匀，这个算法就越快。

杂谈

写完这个算法之后，我觉得有似曾相识的感觉，大家了解通信原理的有没有一样的感觉？
如果把这段不减整数映射到频域，那么这就是递增阶梯的方波，问题就是确定其最长一段方波，如果这个方波太长，数据量太大，我们可以对其特征点采样来压缩数据，根据奈奎斯特采样定理（或者叫香农采样定理）：

当采样频率fs.max大于信号中最高频率fmax的2倍时(fs.max>2fmax)，采样之后的数字信号完整地保留了原始信号中的信息。

上文的2N分采样与此正好相似，是不是很有趣～

（描述的比较乱，大家如果有建议请指正）

Answer 2

不减整数是什么意思？

如果增长，则increment = 1
什么意思？

除了这两点你需要的就是一个大小为10的数组，然后foreach每个字符统计一个就好了。

int topDigit(string n) { //这是不知道什么语言的伪代码
    static int a[10];
    for (char ch : n) {
        a[ch - '0']++;
    }
    int maxCnt = a[0];
    int max = 0;
    for (int i = 1; i < 10; i++) {
        if (maxCnt < a[i]) {
            maxCnt = a[i];
            max = i;
        }
    }
    return max;
}

Answer 3

二分。
看题意好像只有0-9这10个数，但如果输入是个数组那就不一定了。
如果只有0-9，假如一共有n个数字，那么重复最多的那一段必然会比 n/10 多，则可以以这个步长把区间分成 10 段，重复最多数字在某些区间一定上下界相等，用这个可以加快查找速度。
如果不是只有0-0，而数字大量重复，则复杂度可以达到O(logn)，最坏情况是O(n)。
遍历每一个数字显然没利用到非降序这个条件，面试的时候必然被pass……

Answer 4

python3

>>> from collections import Counter
>>> d=Counter(str(11111223333))
>>> int(max(d,key=lambda k:d[k]))
1

Answer 5

@一代键客
方法不错 但是查找也时扫全部 如果数量大就麻烦了 比如 到 1000000 空间复杂度就时1000000 还不如 跳着查 这样效率可能比较高
例如：
假设现在暂存1是最多出现次数且
12-位置是X 1出现次数为Y 直接调到 X+Y位进行判断
if（f(X+Y)==2）{

往后遍历Y` 直到出现23- 并记录位置 X`
MAX = 2；
X = X`;
Y = Y+Y`;
继续；

}else if（f（X+Y）>2）{

temp = f（X+Y）；
往前遍历 直到出现 temp-1 temp - 位置 X`` 偏移量为 Y``;
往后遍历 直到出现 temp temp+1 位置 X``` 偏移量 Y```;
if(Y``+Y```>Y){
    MAX = temp；
    X = X```;
    Y = Y``+Y```;
    继续；
}
继续；

}

Answer 6

提供一种最基础的方法，用javascript实现的findMaxCountNum函数如下：

function findMaxCountNum(str) {
  str += '';
  var num = +str[0];
  var count = 0;
  var maxCount = 0;
  var numArr = [];
  var maxCountArr = [];
  str
    .split('')
    .sort()
    .map(function (item) {
      if (+ item === num) {
        count++;
      } else {
        if (count > maxCount) {
          maxCount = count;
        }
        numArr.push(num);
        maxCountArr.push(count);
        num = +item;
        count = 1;
      }
    });
  if (count > maxCount) {
    maxCount = count;
  }
  numArr.push(num);
  maxCountArr.push(count);
  return numArr[maxCountArr.indexOf(maxCount)];
}
findMaxCountNum(1111124263333)

Answer 7

function count(num){
    //只为演示，不做类型检查
    num += '';
    var len = num.length;
    var lastNum = num[len - 1];
    var max = num[0];
    var maxLen = -(1 / 0);
    for(var i = num[0] * 1 + 1; i <= lastNum; i++){
      var dis = num.indexOf(i) - num.indexOf(i - 1);
      if(dis > maxLen){
        maxLen = dis;
        max = i - 1;
      }
    }
    if(lastNum - num.indexOf(lastNum - 1) > max){
      max = lastNum;
    }
    return max;
  }
  var num = '1122333444445';
  count(num);

Answer 8

'11111223333'.match(/(d)1+/g) =>
["11111", "22", "3333"]
写个循环 顶多也就9个字符串 比较下长度那个最长