c-在一个不在另一个数组中的数组中查找最小的数字

Question

当前我正在尝试解决此任务：给出两个数组，每个数组包含五个整数。查找第一个数组中不在第二个数组中的最低数字。

在我看来，如果用户在第一个数组中输入这样的整数：

0 1 2 3 4 

第二个数组的整数：

0 2 3 4 5

根据任务的条件，最小的整数将是1，因为它不在第二个数组中。这是我的代码：

#include <stdio.h>
#include <locale.h>
int main() {
setlocale(LC_ALL, "Rus");
int arr1[5]; //initialize arrays
int arr2[5];
printf("Enter integersn");
for (int i = 0; i < 5; i++) {
int element;
scanf_s("%d", &element); 
arr1[i] = element;
}
printf("Enter integersn");
for (int i = 0; i < 5; i++) {
int element;
scanf_s("%d", &element); 
arr2[i] = element;
}
int min1 = arr1[0];
int min2 = arr2[0];
for (int i = 0; i < 5; i++) { // algorithm for finding the minimum number of an array 1
if (min1 > arr1[i]) {
min1 = arr1[i];
}
if (min2 > arr2[i]) {
min2 = arr2[i];
}
}
}

好吧，代码很清楚，但下面是如何进行检查，如果第一个数组输入0 1 2 3 4，第二个输入0 2 3 4 5，那么如何去除这个零。

Answer 1

存在一些问题。。。

1. 我们不关心arr2的最小值——只关心arr1
2. 我们必须扫描所有arr2值，以匹配arr1的当前/候选值
3. 有些特殊情况我们必须处理

通常，如果我们只是在arr1中寻找最小值(例如，arr2是而不是一个因子(，我们可以做[正如您所做的]：

int min1 = arr1[0];

并且，我们可以在for循环中从1开始索引到arr1。

但是，如果

1. arr1[0]是arr1中的最小值，该值在arr2中是
2. arr1和arr2具有相同的值[即使它们的顺序不同]

因此，我们需要一个额外的[布尔值]来表示min1值是否有效。并且，我们必须在for循环中从0开始索引。

这是重构后的代码。注释：

#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <locale.h>
#define A1MAX   5
#define A2MAX   5
int
main(void)
{
setlocale(LC_ALL, "Rus");
// define arrays
int arr1[A1MAX];
int arr2[A2MAX];
printf("Enter integersn");
for (int i = 0; i < A1MAX; i++) {
if (scanf("%d", &arr1[i]) != 1) {
printf("missing arr1[%d] -- %sn",i,strerror(errno));
return 2;
}
}
printf("Enter integersn");
for (int i = 0; i < A2MAX; i++) {
if (scanf("%d", &arr2[i]) != 1) {
printf("missing arr2[%d] -- %sn",i,strerror(errno));
return 3;
}
}
int nomin = 1;
int min1 = arr1[0];
// check all values in arr1
for (int i = 0; i < A1MAX; i++) {
// current value we're going to test
int val = arr1[i];
// check value if it's a _new_ minimum or we do _not_ yet have a minimum
if ((val < min1) || nomin) {
// scan all elements of arr2, looking for a match to the current
// arr1 value
int match = 0;
for (int j = 0; j < A2MAX; j++) {
match = (val == arr2[j]);
if (match)
break;
}
// if the current value is _not_ in arr2, we have a new minimum
if (! match) {
min1 = val;
nomin = 0;
}
}
}
if (nomin)
printf("there are no elements in arr1 that are not in arr2n");
else
printf("the minimum element in arr1 not in arr2 is: %dn",min1);
return nomin;
}

Answer 2

由于代码试图将多个索引维护到多个数组中，事情变得复杂。。。如果重用代码并分解函数(也可以测试用户输入(，事情就会简化。。。

#include <stdio.h>
void fill( int arr[], size_t sz ) { // Get user input (with checking)
printf("Enter integersn");
for( size_t i = 0; i < sz; i++ )
if( scanf( "%d", &arr[i] ) != 1 ) {
fprintf( stderr, "scanf failuren" );
exit(1);
}
}
// Search for a value in an array. Return index if found, or size if not found
size_t hunt( int val, int arr[], size_t sz ) {
for( size_t i = 0; i < sz; i++ )
if( val == arr[i] )
return i;
return sz;
}
int main() {
#if 0 // Normal with user entry
int arr1[5], arr2[5];
size_t a1sz = sizeof arr1/sizeof arr1[0];
size_t a2sz = sizeof arr2/sizeof arr2[0];
fill( arr1, a1sz );
fill( arr2, a2sz );
#else // less tedious with compile time init of data
int arr1[] = { 0, 1, 2, 3, 4 };
int arr2[] = { 0, 2, 3, 4, 5 };
size_t a1sz = sizeof arr1/sizeof arr1[0];
size_t a2sz = sizeof arr2/sizeof arr2[0];
#endif
size_t gotOne = 0;
for( size_t i = 0; i < a1sz; i++ ) {
// don't bother testing values if got a candidate and value is larger
if( gotOne && arr1[i] >= arr1[ gotOne ] ) continue;
// following is TRUE when not found...
if( hunt( arr1[i], arr2, a2sz ) == a2sz )
gotOne = i + 1;
}
if( gotOne )
printf( "Smallest in arr1 not in arr2 = %un", arr1[ gotOne - 1 ] );
else
puts( "No such value matching criteria" );
return 0;
}

Smallest in arr1 not in arr2 = 1

Answer 3

算法

对此，最简单的方法是嵌套几个循环，这种方法对小型数据集非常有效。这种方法的时间复杂性增长得非常快。其中m是第一阵列的长度并且n是第二阵列的长度。

幸运的是，我们可以用一种不涉及嵌套循环的方式来处理这个问题。这假设两个数组都只包含唯一的值。如果它们有重复项，则在执行以下操作之前，必须先删除这些重复项。

让我们从几个简单的数组开始：

int foo[] = {1, 4, 7, 9, 2};
int bar[] = {4, 1, 6, 7, 3};

让我们把它们组合成另一个数组。这是一个线性运算。

{1, 4, 7, 9, 2, 4, 1, 6, 7, 3}

然后让我们使用qsort对它们进行排序。此操作通常为O(n*logn(。

{1, 1, 2, 3, 4, 4, 6, 7, 7, 9}

现在，我们可以对这些元素进行线性循环，找到唯一的元素。这些是一个数组中存在的，而不是两个中存在的。

{2, 3, 6, 9}

但这并不能告诉我们哪个在第一个数组中。这听起来像是一个嵌套循环问题。不过，让我们将其与第一个数组相结合。

{1, 4, 7, 9, 2, 2, 3, 6, 9}

我们将对此进行分类。

{1, 2, 2, 3, 4, 6, 7, 9, 9}

现在我们将扫描第一个重复的数字。

2

实施

注意：是否检查malloc错误。

#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
int c = *(const int *)a;
int d = *(const int *)b;
if (c == d) return 0;
else if (c < d) return -1;
else return 1;
}
int min_not_in_2nd_array(int *result, int *arr1, size_t m, int *arr2, size_t n) {
int *temp = malloc(sizeof(int) * (m + n));
//if (!temp) return 0;
for (size_t i = 0; i < m; ++i) temp[i] = arr1[i];
for (size_t i = 0; i < n; ++i) temp[m+i] = arr2[i];
qsort(temp, m+n, sizeof(int), cmp);
int *uniques = malloc(sizeof(int) * (m + n));
//if (!uniques) return 0;
size_t n_uniques = 0;
int cur = temp[0] - 1;
size_t cur_count = 0;
for (size_t i = 0; i < m+n; ++i) {
if (i == m+n-1 && temp[i] != temp[i-1]) {
uniques[n_uniques++] = temp[i]; 
}
else if (temp[i] != cur) {
if (cur_count == 1) uniques[n_uniques++] = cur; 
cur = temp[i];
cur_count = 1;
}
else {
cur_count++;    
}
}
//for (size_t i = 0; i < n_uniques; ++i) printf("%d ", uniques[i]);
//printf("n");

int *temp2 = malloc(sizeof(int) * (m + n_uniques));
// if (!temp2) return 0;

for (size_t i = 0; i < m; ++i) temp2[i] = arr1[i];
for (size_t i = 0; i < n_uniques; ++i) temp2[m+i] = uniques[i];

qsort(temp2, m+n_uniques, sizeof(int), cmp);

int found = 0;

for (size_t i = 0; i < m+n_uniques-1; ++i) {
if (temp2[i] == temp2[i+1]) {
*result = temp2[i];
found = 1;
break;
}
}
free(temp);
free(uniques);
free(temp2);
return found;
}
int main(void) {
int foo[] = {1, 4, 7, 9, 2};
int bar[] = {4, 1, 6, 7, 3};
int baz;
if (min_not_in_2nd_array(&baz, foo, sizeof(foo)/sizeof(*foo), 
bar, sizeof(bar)/sizeof(*bar))) {
printf("Min not in 2nd array is %dn", baz);
}
else {
printf("All elements shared.n");
}
return 0;
}