C#:O(n²) 解决方案，用于查找大小为 n 且数字为 k 的数组的 n/k 个元素

Question

Link where I got the problem from

我正在尝试一个 O(n²) 的解决方案来查找哪些元素在给定数组中出现的次数多 n/k 次(在这种情况下 n=8 - 所以超过两次) .我相信我有解决方案，但我似乎无法弄清楚为什么输出(如下所示)不是 [2、3]。我知道出现的是索引 i = 3 处的元素 2，但我认为 if (count > (arr.Length/k)) 条件会解决这个问题。

int[] arr = { 3, 1, 2, 2, 1, 2, 3, 3 };
int k = 4, count = 1;

for(int i = 0; i < arr.Length; i++)
{
    for (int j = i + 1; j < arr.Length; j++)
    {
        if (arr[i] == arr[j])
        {
            count++;
            if (count > (arr.Length / k))
            {
                Console.WriteLine(arr[i] + " " + i);
                count = 1;
            }
        }
    }
}

输出:

3 0

2 2

2 3

Answer 1

问题是您只重置了 count当有匹配项和 count大于 arr.Length/k .您需要在内部 for 的末尾重置它循环或更好的是在内部 for 之前定义它循环，因为在该循环之外不需要它。另外我猜你会想在 count 后立即跳出这个循环。满足你的条件，否则你会一直写同样的东西。

int[] arr = { 3, 1, 2, 2, 1, 2, 3, 3 };
int k = 4;

for(int i = 0; i < arr.Length; i++)
{
    int count = 1;
    for (int j = i + 1; j < arr.Length; j++)
    {
        if (arr[i] == arr[j])
        {
            count++;
            if (count > (arr.Length / k))
            {
                Console.WriteLine(arr[i] + " " + i );
                break;
            }
        }
    }
}

但是，这仍会在其他位置产生重复值的结果。例如，k 等于 4 的数组 {3, 1, 2, 2, 1, 2, 3, 3, 3, 3, 3, 3} 产生 3,0； 3,6; 3,7;和 3,8。假设您只想要 3,0，那么更好的解决方案是。

int[] arr = { 3, 1, 2, 2, 1, 2, 3, 3 };
int k = 4;    

var results = arr.Select((x,i) => new {Value = x, Index = i})
    .GroupBy(x => x.Value)
    .Where(grp => grp.Count() > arr.Length / k)
    .Select(grp => grp.First());

foreach(var r in results)
{
    Console.WriteLine($"{r.Value} {r.Index}");
}

或者如果您更愿意坚持使用 for循环而不是 Linq 那么你只需要一个 HashSet<int>跟踪您已经看到的值。

int[] arr = { 3, 1, 2, 2, 1, 2, 3, 3 };
int k = 4;
HashSet<int> seen  = new HashSet<int>();

for(int i = 0; i < arr.Length; i++)
{
    if(!seen.Add(arr[i]))
    {
        continue;
    }

    int count = 1;
    for (int j = i + 1; j < arr.Length; j++)
    {
        if (arr[i] == arr[j])
        {
            count++;
            if (count > (arr.Length / k))
            {
                Console.WriteLine(arr[i] + " " + i );
                break;
            }
        }
    }
}

请注意 Add当值已经在哈希集中时返回 false。