二维数组中的数字的最大显示 [英] max shows of number in two dimension array

问题描述

我有一个二维数组，我知道：

I have a two dimensional array and I know:

• 行数和每行的长度


• 每行只包含正数


• 每行都被排序


• 不用于辅助数组
  - 不使用与数据结构

• The number of lines and the length of each line
• Each line contains just positive numbers
• Each line is sorted
• not use with auxiliary array -not use with data structures

以有效的方式在整个数组中出现最大次数。
我已经尝试遍历数组，但是效率不高。

I need to return the number which appears max times in the the whole array in an efficient way. I already tried to pass all over the array but it's not efficient.

这是数组的一个例子。

{
  {5, 7, 8},
  {6, 6},
  {null},
  {5, 6, 8, 9}
}

此示例的预期返回值是6。

The expected return value for this example is 6.

我想获得c ++中的解释或代码

I would like to get the explanation or code in c++

感谢

推荐答案

由于需要C / C ++解决方案，因此可以使用2D数组。
所有缺失值可以由-1（或在搜索中涉及的有效数字中不期望的任何数字）表示。
所以一个空行可以用-1表示。请参阅下面的代码。
由于在C / C ++中，2D数组在内存中连续表示。因此，我们可以将二维数组转换为一维数组。
现在我们可以对数组进行排序。排序后，所有的'-1'将在开始，可以被丢弃。
从剩下的元素我们可以找到一个元素的最大频率。

Since a C/C++ solution is required then a 2D Array can be used. All the missing values can be represented by -1 (or any number which is not expected in valid numbers involved in search). So a empty row can be represented by all -1. See the code below. Since in C/C++, 2D array is continuously represented in memory. So we can convert 2D array to 1D array. Now we can sort the array. After sorting, all the '-1' will be at the beginning which can be discarded. From the leftover elements we can find the max frequency of an element.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main()
{
    int i, prev, max = -1, count = 0, maxvalue = -1;
    int a[4][4] = {{5, 7, 8, -1}, {6, 6, -1, -1}, {-1, -1, -1, -1}, {5, 6, 8, 9}};
    //int a[4][4] = {{-1, -1, -1, -1}, {-1, -1, -1, -1}, {-1, -1, -1, -1}, {-1, -1, -1, -1}};

    int *b = (int*)a;
    int total = sizeof(a) / sizeof(int);

    qsort(b, total, sizeof(int), compare);

    for(i = 0; i < total; ++i)
    {
            if(b[i] != -1)
            {
                    break;
            }
    }

    //printf("\n");

    i = i + 1;

    prev = -1;
    count = 0;
    if(i < total)
    {
            prev = b[i];
            count = 1;
    }
    for(i = i + 1; i < total; ++i)
    {
            //printf("prev=%d, b[i]=%d, max=%d, count=%d\n", prev, b[i], max, count);

            if(prev == b[i])
            {
                    count++;;
            }
            else
            {
                    if(max < count)
                    {
                            max = count;
                            maxvalue = prev;
                    }
                    prev = b[i];
                    count = 1;
            }
    }

    if(max != -1)
    {
            printf("Max Occurence of %d = %d\n", maxvalue, max);
    }
    else
    {
            printf("All the rows are of zero length\n");
    }

    return 0;
}
//Output:
Max Occurence of 6 = 3

这篇关于二维数组中的数字的最大显示的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！