找到int []数组中最受欢迎的元素

Question

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

我该怎么写一个方法并返回7？

我希望在没有列表,地图或其他助手的帮助下保持原生.只有数组[].

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 : 0);
}

现在,我们找到具有最大频率的数字并将其返回:

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;

}

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;
}

Answer 3

1. 拿一张地图来映射元素 - >计数
2. 迭代数组并处理地图
3. 迭代地图,找出流行的

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);

Answer 5

使用 Java 8 流

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数组转换为装箱的整数流。然后我们groupingBy在元素上收集 by并使用辅助计数收集器在groupBy.

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