首页 > 数学相关 > 找出重复次数最多的数字
2014
08-05

找出重复次数最多的数字

问题

给定一个大小为n的数组,该数组包含数字的范围在 [0...k-1], k是一个正整数,k < = n。在这个数组找到重复次数最多的数字。

例如, 假设k= 10给定的数组是arr[] = {1, 2, 2, 2, 0, 2, 0, 2, 3, 8, 0, 9, 2, 3},最大的重复数量将是2。

期望的时间复杂度是O(n),空间复杂度为O(1),允许修改原数组。

分析

比较直接的解法是使用双重循环,逐个判断每个元素出现的次数,复杂度为O(n^2). 改进的做法是,使用哈希,用一个大小为k的数组count[] ,用来记录每个数字出现的次数,count[arr[i]]. 就代表 arr[i]重复的次数。这种方法遍历一次即可,但是空间复杂度为 O(k).

注意题目中的另一个条件,可以修改原数组,因此可以考虑用原数组代替 count[] 数组,为了能保证修改之后还要用到原来的数据,修改应该是可恢复的。数据范围在 [0...k-1] 内也是一个很重要的条件。这里需要用到一些简单的数学知识即可。

方法是:遍历arr[]中的元素,做如下操作 arr[arr[i]%k] += k .  之所以增加k是因为可以恢复修改过的arr[i],它最初的数据即为 arr[i] % k , 同时 arr[i] / k 就代表数字 i 出现的次数。此方法的前提是要保证计算不会溢出。

下面是Java代码实现

//============================================================================
// Name        : MaxReaption.java
// Author      : GaoTong
// Date        : 2014/8/3
// Copyright   : www.acmerblog.com
//============================================================================
public class MaxReapting {

    static int maxRepeating(int[]arr, int k){
        int maxCnt = 0; // maxCnt/k 为当前最大的重复次数
        int ans = arr[0];
        for (int i = 0; i< arr.length; i++){
            arr[arr[i]%k] += k;
            // arr[arr[i]%k] / k  代表 arr[i]%k 出现的次数, 由于k是固定的,这里可以直接用arr[arr[i]%k]比较
            if(maxCnt < arr[arr[i]%k]){
                maxCnt = arr[arr[i]%k];
                ans = arr[i]%k;
            }
        }

        //恢复数组
        for (int i = 0; i< arr.length; i++){
            arr[i] = arr[i] % k;
        }
        return ans;
    }

    public static void main(String args[]){
        int arr[] = {2, 3, 3, 5, 7,3, 7,4, 1,7,7};
        int k = 8;
        System.out.println("The maximum repeating number is : " + maxRepeating(arr, k));

    }
}

参考:http://www.geeksforgeeks.org/find-the-maximum-repeating-number-in-ok-time/


  1. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!