在int[]数组中找到最流行的元素

Question

int[] a = new int[10]{1,2,3,4,5,6,7,7,7,7};

如何编写一个返回7的方法？

我想在不使用列表、映射或其他助手的情况下保持原生。只能用数组[]。

- SexyMF

---

可能是重复问题：https://dev59.com/1HI-5IYBdhLWcg3wcn3m，https://dev59.com/XlHTa4cB1Zd3GeqPOQ0a。 - dbf

Answer 1

试着使用这个答案。首先，是数据：

int[] a = {1,2,3,4,5,6,7,7,7,7};

这里，我们建立一个地图来计算每个数字出现的次数：

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i : a) {
    Integer count = map.get(i);
    map.put(i, count != null ? count+1 : 1);
}

现在，我们找到具有最大频率的数字并返回它：

Integer popular = Collections.max(map.entrySet(),
    new Comparator<Map.Entry<Integer, Integer>>() {
    @Override
    public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {
        return o1.getValue().compareTo(o2.getValue());
    }
}).getKey();

正如您所看到的，最流行的数字是七：

System.out.println(popular);
> 7

编辑

这是我的答案，不使用映射、列表等数据结构，仅使用数组；虽然我在原地对数组进行排序。它的时间复杂度为O（n log n），比O（n ^ 2）的接受方案更好。

public int findPopular(int[] a) {

    if (a == null || a.length == 0)
        return 0;

    Arrays.sort(a);

    int previous = a[0];
    int popular = a[0];
    int count = 1;
    int maxCount = 1;

    for (int i = 1; i < a.length; i++) {
        if (a[i] == previous)
            count++;
        else {
            if (count > maxCount) {
                popular = a[i-1];
                maxCount = count;
            }
            previous = a[i];
            count = 1;
        }
    }

    return count > maxCount ? a[a.length-1] : popular;

}

- Óscar López

---

在空引用或长度为0的情况下返回0并不是一个好主意，因为在这种情况下0很可能是一个有效的元素。 - Haggra

在计算出现次数的映射中，如果计数为null，则表示找到的元素是第一次出现，那么为什么不将1放入其中，而是放入0呢？ - Massimiliano Giunchi

@MassimilianoGiunchi 你是对的！感谢你发现了那个错误，现在已经修复了。 - Óscar López

Answer 2

public int getPopularElement(int[] a)
{
  int count = 1, tempCount;
  int popular = a[0];
  int temp = 0;
  for (int i = 0; i < (a.length - 1); i++)
  {
    temp = a[i];
    tempCount = 0;
    for (int j = 1; j < a.length; j++)
    {
      if (temp == a[j])
        tempCount++;
    }
    if (tempCount > count)
    {
      popular = temp;
      count = tempCount;
    }
  }
  return popular;
}

- nIcE cOw

---

谢谢您提供的解决方案。我感到惊讶的是您的答案被接受为正确答案，因为在计算机科学中通常o(n2)不是最好的答案。但是，您的解决方案肯定更易于理解、简单直观。哇，您在Stackoverflow上得分很高啊，向您致敬！ - Abhijit Gaikwad

@gabhi：我在看完OP的问题后立刻就做出来了。虽然我没有考虑太多复杂性方面的问题，但如果你能做出一个更好的，我会立刻点赞的 :-) - nIcE cOw

我猜把每个整数出现的频率放进一个哈希表里可以将时间复杂度降至线性。 - human.js

@nIcEcOw 即使有人不得不使用两个循环，我仍然认为这里有改进的余地。请看我的答案。 - M Sach

如果我们使用任意字符串作为输入，而非整数字符串，你的代码会有很多变化吗？（例如："今天是8月6日aaa"，则最常见的字母为 a） - user8422515

@t.Anne：抱歉回复晚了。如果你想将上述算法用于“String”，只需将方法参数更改为char []数组，返回类型更改为char，并将变量popular和temp的数据类型更改为char。然后可以通过调用getPopularElement(text.toCharArray())来使用该方法，其中text是String text = "today is 6th august aaa";。这样可能会起作用。 - nIcE cOw

Answer 3

1. 将地图映射到元素 -> 数量
2. 遍历数组并处理地图
3. 遍历地图并找出流行的地方

- jmj

---

好的回答。你可能想提到，如果原始数字限制在相对较小的最大值（比如100或1000），你可以使用数组而不是映射表。 - Sergey Kalinichenko

@dasb Map很好，我没有看到它有任何缺点，也没有看到它比数组有任何优势。 - jmj

如何使用临时数组进行本地化处理？ - SexyMF

@dasb 对于刚接触Java的程序员来说，数组比映射更容易理解。考虑到问题的措辞（以及问题本身的内容），我毫不怀疑OP是新手（不仅是在Java编程方面）。这很可能是他的作业。 - Sergey Kalinichenko

现在你有一个数据数组，需要的是计数数组。例如，如果你的数据数组中第0个元素是1，第1个元素是2，那么在你的计数数组中应该保存1，这是1的计数，以此类推... - jmj

@JigarJoshi 数组比映射更好，因为读/写时间为O(1)。使用哈希映射，读/写时间为O(1)预期，使用树映射，读/写时间为O(lg n)。 - John Kurlak

Answer 4

假设你的数组已经排好序（就像你发布的那个），你可以简单地遍历数组并计算元素的最长片段，这类似于@narek.gevorgyan的帖子，但没有那么大的数组，并且无论数组的大小如何，它使用相同数量的内存：

private static int getMostPopularElement(int[] a){
    int counter = 0, curr, maxvalue, maxcounter = -1;
    maxvalue = curr = a[0];

    for (int e : a){
        if (curr == e){
            counter++;
        } else {
            if (counter > maxcounter){
                maxcounter = counter;
                maxvalue = curr;
            }
            counter = 0;
            curr = e;
        }
    }
    if (counter > maxcounter){
        maxvalue = curr;
    }

    return maxvalue;
}


public static void main(String[] args) {
    System.out.println(getMostPopularElement(new int[]{1,2,3,4,5,6,7,7,7,7}));
}

如果数组没有排序，则使用Arrays.sort(a);进行排序。

- Federico Vera

Answer 5

使用Java 8 Streams

int data[] = { 1, 5, 7, 4, 6, 2, 0, 1, 3, 2, 2 };
Map<Integer, Long> count = Arrays.stream(data)
    .boxed()
    .collect(Collectors.groupingBy(Function.identity(), counting()));

int max = count.entrySet().stream()
    .max((first, second) -> {
        return (int) (first.getValue() - second.getValue());
    })
    .get().getKey();

System.out.println(max);

解释

我们将int[] data数组转换为装箱后的Integer流。然后我们按元素进行groupingBy收集，使用次要计数收集器进行计数。

最后，我们使用流和lambda比较器根据计数再次对元素->计数的映射进行排序。

- faizan

Answer 6

这是一个没有地图的例子:

public class Main {       

    public static void main(String[] args) {
        int[] a = new int[]{ 1, 2, 3, 4, 5, 6, 7, 7, 7, 7 };
        System.out.println(getMostPopularElement(a));        
    }

    private static int getMostPopularElement(int[] a) {             
        int maxElementIndex = getArrayMaximumElementIndex(a); 
        int[] b = new int[a[maxElementIndex] + 1]

        for (int i = 0; i < a.length; i++) {
            ++b[a[i]];
        }

        return getArrayMaximumElementIndex(b);
    }

    private static int getArrayMaximumElementIndex(int[] a) {
        int maxElementIndex = 0;

        for (int i = 1; i < a.length; i++) {
            if (a[i] >= a[maxElementIndex]) {
                maxElementIndex = i;
            }
        }

        return maxElementIndex;
    }      

}

如果您的数组可能有元素小于< 0，则只需更改一些代码即可。

当您的数组项不是大数字时，此算法非常有用。

- narek.gevorgyan

Answer 7

如果您不想使用地图，则只需按照以下步骤操作：

1. 对数组进行排序（使用Arrays.sort()）
2. 使用一个变量来保存最流行的元素（mostPopular），一个变量来保存它在数组中出现的次数（mostPopularCount），以及一个变量来保存迭代中当前数字的出现次数（currentCount）
3. 遍历数组。如果当前元素与mostPopular相同，则增加currentCount。如果不是，则将currentCount重置为1。如果currentCount > mostPopularCount，则将mostPopularCount设置为currentCount，并将mostPopular设置为当前元素。

- JB Nizet

---

是的，这显然比我的答案好。 - narek.gevorgyan

但是也许他的数组大小很大，数字很小。在这种情况下，我的更好。 - narek.gevorgyan

Answer 8

看起来你正在寻找模式值（统计模式），请查看Apache的文档了解统计函数。

- Lalith B

Answer 9

package frequent;

import java.util.HashMap;
import java.util.Map;

public class Frequent_number {

    //Find the most frequent integer in an array

    public static void main(String[] args) {
        int arr[]= {1,2,3,4,3,2,2,3,3};

        System.out.println(getFrequent(arr));
        System.out.println(getFrequentBySorting(arr));
    }

    //Using Map , TC: O(n)  SC: O(n)
    static public int getFrequent(int arr[]){
        int ans=0;
        Map<Integer,Integer> m = new HashMap<>();
        for(int i:arr){
            if(m.containsKey(i)){
                m.put(i, m.get(i)+1);
            }else{
                m.put(i, 1);
            }
        }
        int maxVal=0;
        for(Integer in: m.keySet()){
            if(m.get(in)>maxVal){
                ans=in;
                maxVal = m.get(in);
            }
        }
        return ans;
    }

    //Sort the array and then find it TC: O(nlogn) SC: O(1)
    public static int getFrequentBySorting(int arr[]){
        int current=arr[0];
        int ansCount=0;
        int tempCount=0;
        int ans=current;
        for(int i:arr){
            if(i==current){
                tempCount++;
            }
            if(tempCount>ansCount){
                ansCount=tempCount;
                ans=i;
            }
            current=i;
        }
        return ans;
    }

}

- Praveen Kumar

Answer 10

对于这个问题，数组元素的值应该小于数组长度：

public void findCounts(int[] arr, int n) {
    int i = 0;

    while (i < n) {
        if (arr[i] <= 0) {
            i++;
            continue;
        }

        int elementIndex = arr[i] - 1;

        if (arr[elementIndex] > 0) {
            arr[i] = arr[elementIndex];
            arr[elementIndex] = -1;
        }
        else {
            arr[elementIndex]--;
            arr[i] = 0;
            i++;
        }
    }

    Console.WriteLine("Below are counts of all elements");

    for (int j = 0; j < n; j++) {
        Console.WriteLine(j + 1 + "->" + Math.Abs(arr[j]));
    }
}

这个时间复杂度为 O(N)，空间复杂度为 O(1)。

- Pavan Tiwari