c-如何检查数组是否包含1到n^2个整数

Question

假设我想检查一个3x3数组，并希望它包含从1到9的所有数字。除了我把它写在下面之外，我想不出其他有效的方法了。有没有更好的方法来解决这个问题？

int i, size, row, col, num = 1, valid = 0;
for(i=0; i<size*size; i++)
    for(row=0; row<size; row++)
        for(col=0; col<size; col++)
            if(num == arr[row][col]) {
                num++;
                valid++;
            }   

Answer 1

是。有更好的方法。

最好使用布尔数组而不是第三个循环。保留一个布尔值数组，最初全部设置为false。对于找到的每个数字，将数组中相应的索引标记为true。在行和列循环结束时，如果数组中的所有条目都设置为true，则会找到所有数字。

为了进一步优化，您可以声明一个计数器变量。每次找到一个数字时，使用布尔数组检查是否已经找到该数字。如果没有，则递增计数器。在循环结束时，如果计数器为9，则您已找到9个唯一的数字。

如果发现重复，您甚至可以提前终止。这将进一步提高性能，但只有当要查找的唯一数字的数量和它们居住的空间的数量相同时才有效。也就是说，如果你有18个空格，并且想检查所有的数字1-9，这是行不通的。

Answer 2

怎么样：

bool nums[9] = {false, false, false, false, false, false, false, false, false};
for (int row = 0; row < 3; ++row) {
   for (int col =0; col < 3; ++col) {
      if (arr[row][col] < 1 || arr[row][col]> 9 || nums[arr[row][col] -1]) {
        // Number is out of range or previous it)
        break;
      }
      nums[arr[row][col] -1] = true;
   }
}

其中，如果已找到相应的值，则nums存储true。

Answer 3

另一个想法是循环遍历k-times-k数组，并对所有元素求和。确保得到的和等于1+2+...+n = n*(n+1) / 2，其中为n = k*k。这与所有元素都是唯一的(并且是正的(条件相结合，确保了数组包含{1,2,...,n}中的所有元素。

对于n=9，您应该检查总和是否等于45。对于小型n，您可以使用位掩码来检查是否已经看到数字：if (n & (1 << current_number)) { seen; } else {not yet seen; mark as seen via n |= (1 << current_number); }

Answer 4

不需要外循环，当您找到第一个不匹配的项目时，您可以停止搜索。除非你出于某种原因需要一份所有不匹配项目的列表，否则情况似乎并非如此(？(。

如果您知道维度总是很小，则可以进行进一步的微观优化。在该示例中，它们被假定为<256:

#include <stdint.h>
#include <stdbool.h>
bool is_arr_ok8 (uint_fast8_t row, uint_fast8_t col, int arr[row][col])
{
  uint_fast8_t count=1;
  for (uint_fast8_t r=0; r<row; r++)
  {
    for(uint_fast8_t c=0; c<col; c++)
    {
      if(arr[r][c] != count)
      {
        return false;
      }
      count++;
    }
  }
  return true;
}

这里最重要的是，最内部的循环对应于最内部的维度。你也可以反过来做，这不会影响算法，但会带来更差的数据缓存性能。