c - 在数组中查找对

Question

所以我想做的是编写代码来查找数组中的一对数字。当只有一对数字时，下面的代码可以完美运行。

#include <stdio.h>

main()
{
    int arr[10], i, j, pairs = 0;
    int n;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
    for (i = 0; i < n; i++)
    {
        for (j = i + 1; j < n; j++)
        {
            if (arr[i] == arr[j])
            {
                pairs++;
            }
        }
    }
    printf("%d", pairs);
}

我想让它在有 3 个相同元素时起作用。例如，arr[5] = 1, 1, 1, 2, 2它应该返回 2 对(1,1 和 2,2 并遗漏了额外的 1)但它返回 4 对而不是我的代码!

Answer 1

我看到了这个问题并想尝试一下，尤其是当@Neil 和我处于同一波长时。

现在是一天后，由于发布了 O(n log n) 和 O(n²) 的解决方案，这里是实际的 O(n) 版本(其中 n 实际上是哈希表的长度，而不是输入，我们不计算)。
_{即使我们计算它，它也将是 O(n+k) → O(n)。}
^{(同样的事情也发生在其他解决方案上，这就是我们不计算输入的原因。)}

#define __STDC_WANT_LIB_EXT1__ 1
#include <math.h>
#include <stdio.h>


// the histogram
enum { MAX_SAMPLES = 1000 };  // this should be overkill for the expected load factor
int values[ MAX_SAMPLES ];    // the sample value being counted
int counts[ MAX_SAMPLES ];    // non-negative, zero == value not sampled


void add( int value )
{
  int hash = abs( value ) % MAX_SAMPLES;  // simplest hash EVER

  for (int offset = 0;  offset < MAX_SAMPLES;  offset++)  // give up if table is saturated
  {
    int index = (hash + offset) % MAX_SAMPLES;

    if (counts[index] == 0)      // if found an empty spot:
      values[index] = value;     //   add the value

    if (values[index] == value)  // if found the value:
    {                            //
      counts[index] += 1;        //   increment value's count
      break;                     //   and done searching
    }
  }
}


int read_int()
{
  int value;
  scanf_s( "%d", &value );
  return value;
}


int main()
{
  // input list --> histogram
  for (int n = read_int();  n;  n--)
    add( read_int() );

  // Σ ⌊count / 2⌋ --> number of pairs
  int num_pairs = 0;
  for (int n = 0;  n < MAX_SAMPLES;  n++)
    num_pairs += counts[n] / 2;

  printf( "%d", num_pairs );
}

此解决方案已被浓缩为最简单的术语。特别是:

• 没有错误检查:没有分配错误，没有输入失败，没有哈希表饱和
• 对直方图使用全局的、固定大小的散列图，意思是:
  • 它不能在需要时生长
  • 但所有计数都方便地自动初始化为零

这个解决方案确实有它的缺点:

• 需要额外的O(k)空间
• 错误的输入会使它陷入困境
  例如，如果所有输入(mod 表大小)都是相同的值，那么每个输入都将是哈希冲突。对散列映射进行更复杂的管理可以缓解这两个问题，但代价是增加了复杂性(如果过载或检测到太多冲突，则增加散列映射)。
  如果表大小是质数，这也会有很大帮助.

输入法

不知道输入一定是{n, a₁, ..., a_n }，也就是至少在学术界很常见，但这让我很烦。

我非常喜欢不需要用户知道他或她打算提供多少项目的输入:只需键入它们并按 Enter。这比人们意识到的要容易得多:

1. 从命令行参数输入(非常非常方便测试/播放):

int main( int argc, char ** argv )
{
  for (int n = 1;  n < argc;  n++)
    add( atoi( argv[n] ) );

1. 从单行文本输入，然后我们对其进行解析:

// using strtok

fgets( s, sizeof(s), stdin );
for (char * token = strtok( s, " " );  token;  token = strtok( NULL, " " ))
  add( atoi( token ) );

// using sscanf

fgets( s, sizeof(s), stdin );
for (int value, k, n = 0;  sscanf_s( s + n, "%d%n", &value, &k ) == 1;  n += k)
  add( value );

这两种输入解决方案很容易组合到同一个程序中:

int main( int argc, char ** argv )
{
  if (argc > 1)
    // get input from command-line arguments //
  else
    // get input from a single line of text //

无论如何，即使使用精简的全局直方图对象减少了代码行，此解决方案对于介绍性作业来说也是完全过分的。

理想情况下，SO 对家庭作业问题的回答应该有助于 OP 完成他或她自己的解决方案(而不是仅仅成为“哦，哦，我能做到”的垃圾场其他人的解决方案，使其不过是为学生提供的免费代码编写服务)。希望这个解决方案只是提供了另一个工具来推理 future 的问题。