C语言中如何检查矩阵中是否存在唯一元素

Question

我需要帮助编写一个程序来检查矩阵中是否存在唯一元素或根本没有。 首先，程序询问行数和列数。然后它询问矩阵的元素。 如果在矩阵中找到唯一元素，则会打印“找到唯一元素”。 如果没有唯一元素，则会打印“No unique element”。

int rows, cols;
 printf("Enter the number of rows: ");
 scanf("%d", &rows);
 printf("Enter the number of columns: ");
 scanf("%d", &cols);
 
 int matrix[rows][cols];
 for(int row = 0; row < rows; row++){
     for(int col = 0; col < cols; col++){
         scanf("%d", &matrix[row][col]);
     }
}

我感谢您的帮助，非常感谢。

Answer 1

即使是 n 维数组在内存中也是线性的。您可以就地对线性数组进行排序并查找唯一元素。

int compare_ints(const void* a, const void* b) {
  const int arg1 = *(const int*)a;
  const int arg2 = *(const int*)b;
 
  if (arg1 < arg2) return -1;
  if (arg1 > arg2) return 1;
  return 0;
 
  // return (arg1 > arg2) - (arg1 < arg2); // possible shortcut
  // return arg1 - arg2; // erroneous shortcut (fails if INT_MIN is present)
}

// ... your Q code here

const size_t n = rows * cols;
int* arr = (int*)matrix;
qsort(arr, n, sizeof(int), compare_ints);
for (size_t i = 0; i < n - 1; i++) {
  if (arr[i] == arr[i + 1]) {
    puts("No unique element.");
    return;
  }
}
puts("Unique element found.");

Answer 2

一种简单的方法是将矩阵解释为一维数组。

例如，

int unique = 0;
size_t n = rows * cols;
int *a = ( int * ) matrix;

for ( size_t i = 0; !unique && i < n; i++ )
{
    size_t j = 0;
    while ( j < i && a[j] != a[i] ) ++j;

    if ( j++ == i )
    {
        while ( j != n && a[j] != a[i] ) ++j;

        unique = j == n;
    }
}  

if ( unique ) puts( "Unique element found." );
else puts( "No unique element." );

要获取唯一元素的行和列，您只需在嵌套循环外部声明变量 i 即可。例如

int *a = ( int * ) matrix;
int unique = 0;
size_t n = rows * cols;
size_t i = 0;

for ( ; !unique && i < n; i += !unique )
{
    size_t j = 0;
    while ( j < i && a[j] != a[i] ) ++j;

    if ( j++ == i )
    {
        while ( j != n && a[j] != a[i] ) ++j;

        unique = j == n;
    }
}  

if ( unique ) 
{
    size_t row = i / cols;
    size_t col = i % cols;
    printf( "Unique element found at %zu row and %zu column.\n", row, col );
}
else 
{
    puts( "No unique element." );
}