检查C中矩阵上的重复数字
Check repeated numbers on a matrix in C
如何使用重复来检查 n x n 矩阵上是否没有任何重复数字？
两次使用两个 for 不会让我检查任何不共享至少一行或一列的内容
示例：（尽可能以最简化的方式）：
int matrix[n][n];
/*matrix is filled*/
int current, isEqual;
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
current = matrix[i][j];
if (current == matrix[i][j+1])
{
isEqual=1;
}
else
{
isEqual=0;
}
}
}
for (int j=0; j<n; j++)
{
for (int i=0; i<n; i++)
{
current = matrix[i][j];
if (current == matrix[i+1][j])
{
isEqual=1;
}
else
{
isEqual=0;
}
}
}
我无法检查不共享行或列的数字。
首先，将 NxM 矩阵视为长度为 [N*M] 的数组。唯一的区别是您访问元素的方式（例如，两个 for 而不是一个）。
然后，一个简单的算法是迭代每个元素（第一个索引），并且对于每个元素，迭代每个 other 元素（第二个索引）以检查它是否相同。使用数组更容易；在矩阵中它是相同的，可能更冗长和复杂。但是算法是一样的
作为第二阶段，实现基本算法后，您可以在第一个索引之后的元素中开始第二个索引来提高其性能。这样，您就可以避免多次检查已经看到的元素。如果你用 2 个 for 迭代它，这种算法改进在矩阵中稍微难一点，因为更难知道什么是“下一个索引”（你有一个“复合”索引，{i，j}）。
执行此操作的一种简单方法是将每个数字插入到数据结构中，以便轻松检查重复项。这在 C 语言中很有趣，虽然以下肯定不是超级高效或生产就绪，但它是 (IMO) 一个不错的小玩具：
/* Check if any integer on the input stream is a dup */
#include <stdio.h>
#include <stdlib.h>
struct node { int data; struct node *child[2]; };
static struct node *
new_node(int data)
{
struct node *e = calloc(1, sizeof *e);
if( e == NULL ){
perror("calloc");
exit(EXIT_FAILURE);
}
e->data = data;
return e;
}
/*
* Insert a value into the tree. Return 1 if already present.
* Note that this tree needs to be rebalanced. In a real
* project, we would use existing libraries. For this toy
* it is not worth the work needed to properly rebalance the
* tree.
*/
int
insert(struct node **table, int data)
{
struct node *t = *table;
if( !t ){
*table = new_node(data);
return 0;
}
if( data == t->data ){
return 1;
}
return insert(&t->child[data < t->data], data);
}
int
main(void)
{
int rv, v;
struct node *table = NULL;
while( (rv = scanf("%d", &v)) == 1 ){
if( insert(&table, v) ){
fprintf(stderr, "%d is duplicated\n", v);
return EXIT_FAILURE;
}
}
if( rv != EOF ){
fprintf(stderr, "Invalid input\n");
return EXIT_FAILURE;
}
return EXIT_SUCCESS;
}
基本方法是遍历 nxn 矩阵并保留其中的数字列表以及每个数字在 nxn 矩阵中找到的次数的计数。
以下是 50 x 50 矩阵的示例源代码。将其扩展到 n x n 矩阵非常简单，我将其作为练习留给您。您可能需要做一些事情，例如使用 malloc() 创建任意大小的矩阵。有这样的帖子。
我也没有说明数据首先是如何放入矩阵的。这也取决于你。
这只是为了展示一种用于确定矩阵中是否存在重复项的蛮力方法。
我还冒昧地假设矩阵元素是 int，但将类型更改为其他内容应该很简单。如果矩阵元素不是简单的数据值类型，例如 int、long 等，那么函数 findAndCount() 将需要更改以进行相等比较。
这是我正在使用的数据结构。
typedef struct {
int nLength; // number of list elements in use
struct {
int iNumber; // number from an element of the nxn matrix
int iCount; // number of times this element was found in the matrix
} list[50 * 50];
} elementList;
elementList matrixList = {
0,
{0, 0}
};
int matrixThing[50][50];
接下来我们需要遍历矩阵，并使用矩阵中的每个元素来检查它是否在列表中。如果不是，则添加它。它确实存在然后增加计数。
for (unsigned short i = 0; i < 50; i++) {
for (unsigned short j = 0; j < 50; j++) {
findAndCount (matrixThing[i][j], &matrixList);
}
}
然后我们需要定义我们用来根据列表检查矩阵值的函数。
void findAndCount (int matrixElement, elementList *matrixList)
{
for (int i = 0; i < matrixList->nLength; i++) {
if (matrixElement == matrixList->list[i].iNumber) {
matrixList->list[i].iCount++;
return;
}
}
// value not found in the list so we add it and set the initial count
// to one.
// we can then determine if there are any duplicates by checking the
// resulting list once we have processed all matrix elements to see
// if any count is greater than one.
// the initial check will be to see if the value of nLength is equal
// to the number of array elements in the matrix, n time n.
// so a 50 x 50 matrix should result in an nLength of 2500 if each
// element is unique.
matrixList->list[matrixList->nLength].iNumber = matrixElement;
matrixList->list[matrixList->nLength].iCount = 1;
matrixList->nLength++;
return;
}
搜索算法
上述函数 findAndCheck() 是一种强力搜索算法，它逐个元素地搜索未排序的列表，直到找到要搜索的内容或到达列表的末尾。
如果列表已排序，那么您可以使用 binary search algorithm which is much quicker than a linear search. However you then run into the overhead needed to keep the list sorted using a sorting algorithm 以便使用二进制搜索。
如果将用于存储找到的值列表的数据结构更改为按有序序列维护值的数据结构，则还可以减少搜索的开销，尽管也会有插入的开销数据结构中的新值。
一种这样的数据结构是树，有多种类型和算法可以通过插入新项目以及搜索树来构建树。请参阅 search tree，其中描述了几种不同类型的树和搜索。
因此，在搜索工作与向数据结构中添加项目的工作之间存在一种平衡。
这是一个检查重复值的示例，这是我们想要的方式。
循环很慢，我们应该使用哈希集或树而不是使用循环。
我假设你没有使用 C++，因为 C++ 标准库有内置的算法和数据结构来高效地完成它。
#include <stdio.h>
/* Search the 'array' with the specified 'size' for the value 'key'
starting from 'offset' and return 1 if the value is found, otherwise 0 */
int find(int key, int* array, int size, int offset) {
for (int x = offset; x < size; ++x)
if (key == array[x])
return 1;
return 0;
}
/* Print duplicate values in a matrix */
int main(int argc, char *argv[]) {
int matrix[3][3] = { 1, 2, 3, 4, 3, 6, 2, 8, 2 };
int size = sizeof(matrix) / sizeof(matrix[0][0]);
int *ptr = (int*)matrix;
for (int x = 0; x < size; ++x) {
/* If we already checked the number, then don't check it again */
if (find(ptr[x], ptr, x, 0))
continue;
/* Check if the number repeats and show it in the console if it does */
if (find(ptr[x], ptr, size, x + 1))
printf("%d\n", ptr[x]);
}
return 0;
}
当你在 C 方面变得更好时，你应该找到或实现一个“哈希集”或“红黑树”，然后使用它。
如何使用重复来检查 n x n 矩阵上是否没有任何重复数字？
两次使用两个 for 不会让我检查任何不共享至少一行或一列的内容
示例：（尽可能以最简化的方式）：
int matrix[n][n];
/*matrix is filled*/
int current, isEqual;
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
current = matrix[i][j];
if (current == matrix[i][j+1])
{
isEqual=1;
}
else
{
isEqual=0;
}
}
}
for (int j=0; j<n; j++)
{
for (int i=0; i<n; i++)
{
current = matrix[i][j];
if (current == matrix[i+1][j])
{
isEqual=1;
}
else
{
isEqual=0;
}
}
}
我无法检查不共享行或列的数字。
首先，将 NxM 矩阵视为长度为 [N*M] 的数组。唯一的区别是您访问元素的方式（例如，两个 for 而不是一个）。 然后，一个简单的算法是迭代每个元素（第一个索引），并且对于每个元素，迭代每个 other 元素（第二个索引）以检查它是否相同。使用数组更容易；在矩阵中它是相同的，可能更冗长和复杂。但是算法是一样的
作为第二阶段，实现基本算法后，您可以在第一个索引之后的元素中开始第二个索引来提高其性能。这样，您就可以避免多次检查已经看到的元素。如果你用 2 个 for 迭代它，这种算法改进在矩阵中稍微难一点，因为更难知道什么是“下一个索引”（你有一个“复合”索引，{i，j}）。
执行此操作的一种简单方法是将每个数字插入到数据结构中，以便轻松检查重复项。这在 C 语言中很有趣，虽然以下肯定不是超级高效或生产就绪，但它是 (IMO) 一个不错的小玩具：
/* Check if any integer on the input stream is a dup */
#include <stdio.h>
#include <stdlib.h>
struct node { int data; struct node *child[2]; };
static struct node *
new_node(int data)
{
struct node *e = calloc(1, sizeof *e);
if( e == NULL ){
perror("calloc");
exit(EXIT_FAILURE);
}
e->data = data;
return e;
}
/*
* Insert a value into the tree. Return 1 if already present.
* Note that this tree needs to be rebalanced. In a real
* project, we would use existing libraries. For this toy
* it is not worth the work needed to properly rebalance the
* tree.
*/
int
insert(struct node **table, int data)
{
struct node *t = *table;
if( !t ){
*table = new_node(data);
return 0;
}
if( data == t->data ){
return 1;
}
return insert(&t->child[data < t->data], data);
}
int
main(void)
{
int rv, v;
struct node *table = NULL;
while( (rv = scanf("%d", &v)) == 1 ){
if( insert(&table, v) ){
fprintf(stderr, "%d is duplicated\n", v);
return EXIT_FAILURE;
}
}
if( rv != EOF ){
fprintf(stderr, "Invalid input\n");
return EXIT_FAILURE;
}
return EXIT_SUCCESS;
}
基本方法是遍历 nxn 矩阵并保留其中的数字列表以及每个数字在 nxn 矩阵中找到的次数的计数。
以下是 50 x 50 矩阵的示例源代码。将其扩展到 n x n 矩阵非常简单，我将其作为练习留给您。您可能需要做一些事情，例如使用 malloc() 创建任意大小的矩阵。有这样的帖子。
我也没有说明数据首先是如何放入矩阵的。这也取决于你。
这只是为了展示一种用于确定矩阵中是否存在重复项的蛮力方法。
我还冒昧地假设矩阵元素是 int，但将类型更改为其他内容应该很简单。如果矩阵元素不是简单的数据值类型，例如 int、long 等，那么函数 findAndCount() 将需要更改以进行相等比较。
这是我正在使用的数据结构。
typedef struct {
int nLength; // number of list elements in use
struct {
int iNumber; // number from an element of the nxn matrix
int iCount; // number of times this element was found in the matrix
} list[50 * 50];
} elementList;
elementList matrixList = {
0,
{0, 0}
};
int matrixThing[50][50];
接下来我们需要遍历矩阵，并使用矩阵中的每个元素来检查它是否在列表中。如果不是，则添加它。它确实存在然后增加计数。
for (unsigned short i = 0; i < 50; i++) {
for (unsigned short j = 0; j < 50; j++) {
findAndCount (matrixThing[i][j], &matrixList);
}
}
然后我们需要定义我们用来根据列表检查矩阵值的函数。
void findAndCount (int matrixElement, elementList *matrixList)
{
for (int i = 0; i < matrixList->nLength; i++) {
if (matrixElement == matrixList->list[i].iNumber) {
matrixList->list[i].iCount++;
return;
}
}
// value not found in the list so we add it and set the initial count
// to one.
// we can then determine if there are any duplicates by checking the
// resulting list once we have processed all matrix elements to see
// if any count is greater than one.
// the initial check will be to see if the value of nLength is equal
// to the number of array elements in the matrix, n time n.
// so a 50 x 50 matrix should result in an nLength of 2500 if each
// element is unique.
matrixList->list[matrixList->nLength].iNumber = matrixElement;
matrixList->list[matrixList->nLength].iCount = 1;
matrixList->nLength++;
return;
}
搜索算法
上述函数 findAndCheck() 是一种强力搜索算法，它逐个元素地搜索未排序的列表，直到找到要搜索的内容或到达列表的末尾。
如果列表已排序，那么您可以使用 binary search algorithm which is much quicker than a linear search. However you then run into the overhead needed to keep the list sorted using a sorting algorithm 以便使用二进制搜索。
如果将用于存储找到的值列表的数据结构更改为按有序序列维护值的数据结构，则还可以减少搜索的开销，尽管也会有插入的开销数据结构中的新值。
一种这样的数据结构是树，有多种类型和算法可以通过插入新项目以及搜索树来构建树。请参阅 search tree，其中描述了几种不同类型的树和搜索。
因此，在搜索工作与向数据结构中添加项目的工作之间存在一种平衡。
这是一个检查重复值的示例，这是我们想要的方式。 循环很慢，我们应该使用哈希集或树而不是使用循环。 我假设你没有使用 C++，因为 C++ 标准库有内置的算法和数据结构来高效地完成它。
#include <stdio.h>
/* Search the 'array' with the specified 'size' for the value 'key'
starting from 'offset' and return 1 if the value is found, otherwise 0 */
int find(int key, int* array, int size, int offset) {
for (int x = offset; x < size; ++x)
if (key == array[x])
return 1;
return 0;
}
/* Print duplicate values in a matrix */
int main(int argc, char *argv[]) {
int matrix[3][3] = { 1, 2, 3, 4, 3, 6, 2, 8, 2 };
int size = sizeof(matrix) / sizeof(matrix[0][0]);
int *ptr = (int*)matrix;
for (int x = 0; x < size; ++x) {
/* If we already checked the number, then don't check it again */
if (find(ptr[x], ptr, x, 0))
continue;
/* Check if the number repeats and show it in the console if it does */
if (find(ptr[x], ptr, size, x + 1))
printf("%d\n", ptr[x]);
}
return 0;
}
当你在 C 方面变得更好时，你应该找到或实现一个“哈希集”或“红黑树”，然后使用它。