共轭复合物对的数量

Question

我需要编写一个函数，用 p1 和 p2 界定的数组中的共轭复数对填充数组 rez。该函数返回放置在数组中的共轭复数对的数量。序列中不得放置重复项。共轭复数对是 a + bi 和 a - bi 形式的对。

这个任务应该使用结构和指针算术来解决。不允许使用辅助阵列。

#include <stdio.h>
typedef struct {
  int im, re;
} complex;
void remove_duplicates(complex *rez, int *number){
    int i,j,k;
    for (i = 0; i < *number; i++) {
    for (j = i + 1; j < *number; j++) {
      if (rez[i].im == rez[j].im && rez[i].re == rez[j].re) {
        for (k = j; k < *number - 1; k++) {
          rez[k].im = rez[k + 1].im;
          rez[k].re = rez[k + 1].re;
        }
        (*number)--;
        j--;
      }
    }
  }
}
int conjugate_complex(complex *p1, complex *p2, complex *rez) {
  int number_of_pairs = 0;
  while (p1 < p2) {
    if (p1->im == p1->re||p1->im == -1*p1->re) {
      number_of_pairs++;
      rez->re = p1->re;
      rez->im = -1*p1->im;
    }
     rez++;
    p1++;
  }
  remove_duplicates(rez,&number_of_pairs);
  return number_of_pairs;
}
int main() {
    int i;
  complex arr1[5] = {{5, 5}, {3, 3}, {-5, -5}, {5, 5}, {-3, 3}};
  complex arr2[5];
  int vel = conjugate_complex(arr1, arr1 + 5, arr2);
  printf("%d\n", vel);
  for (i=0; i<vel; i++)
    printf("(%d,%d) ",arr2[i].im,arr2[i].re);
  return 0;
}

输出应该是：

4
(-5,5) (-3,3) (5,-5) (3,3)

我的输出是：

5
(-5,5) (-3,3) (5,-5) (-5,5) (3,3)

我的代码的问题是它打印重复项。 你能帮我修复我的remove_duplicates功能吗？ 如果我在主函数中调用它，它就会起作用。但是，我需要在函数 conjugate_complex 中调用它。

Answer 1

要了解为什么拥有一些 O(n) 空间会很好，请考虑一下您在现实生活中会使用方格纸做什么。取出每个复数并在图中放置一个点(re, abs(im))。这样，任何重复项都会合并为一个。该解决方案的复杂度为O(n)。 （预计，哈希值的大小为 O(n) ，因此您必须丢弃一些信息，这将导致冲突。）

最好首先不要重复元素。无论您是否使用 布隆过滤器 来绕过没有数组的限制，O(n) 哈希、O(n log n) 排序或 O(n^2) 方法（可以说是最简单的）最好有这个功能，（在伪代码中， 是 C99，使用 int，装饰除外）：

boolean pair_is_equal(pair a, pair b)

请注意，pair 是在语义上不等同于复杂。您可以使用相同的表示形式（您一直在使用这种表示形式，并且考虑到输出格式，这是最简单的），但请注意它们表示不同的事物。如果您让一个complex代表一个pair：

boolean pair_is_equal(complex a, complex b)

那么您还必须检查a或b之一> 的复共轭，（除了 Im[a] == 0 || Im[b] == 0。）关心 2 的补码 INT_MIN，超出了范围abs 并且不会有补集（如何测试。）