目前我正在嘗試解決這個任務：給出兩個陣列，每個陣列有五個整數。在第一個陣列中找到第二個陣列中沒有的最小數。
在我看來，如果用戶在第一個陣列中輸入這樣的整數：
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 integers\n");
for (int i = 0; i < 5; i ) {
int element;
scanf_s("%d", &element);
arr1[i] = element;
}
printf("Enter integers\n");
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那么如何洗掉這個零。
uj5u.com熱心網友回復：
代碼嘗試將多個索引維護到多個陣列中，事情變得復雜......如果您重用代碼并分解函式（也可以測驗用戶輸入），事情就會變得簡單......
#include <stdio.h>
void fill( int arr[], size_t sz ) { // Get user input (with checking)
printf("Enter integers\n");
for( size_t i = 0; i < sz; i )
if( scanf( "%d", &arr[i] ) != 1 ) {
fprintf( stderr, "scanf failure\n" );
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 = %u\n", arr1[ gotOne - 1 ] );
else
puts( "No such value matching criteria" );
return 0;
}
Smallest in arr1 not in arr2 = 1
uj5u.com熱心網友回復：
演算法
最簡單的方法是嵌套幾個回圈，并且非常適用于小型資料集。這種方法的時間復雜度增長非常快。O(m*n) 其中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*log n)。
{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 %d\n", baz);
}
else {
printf("All elements shared.\n");
}
return 0;
}
uj5u.com熱心網友回復：
有一些問題...
- 我們不關心
arr2--only for的最小值arr1 - 我們必須掃描所有
arr2值以匹配當前/候選值arr1 - 有一些特殊情況我們必須處理
通常，如果我們只是在尋找最小值arr1（例如arr2不是一個因素），我們可以[就像你所做的那樣]：
int min1 = arr1[0];
而且，我們可以在回圈arr1中從 1開始索引。for
但是，如果：
arr1[0]是最小值arr1，該值在arr2arr1并arr2具有相同的值[即使它們的順序不同]。
因此，我們需要一個額外的 [boolean] 值來表示該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 integers\n");
for (int i = 0; i < A1MAX; i ) {
if (scanf("%d", &arr1[i]) != 1) {
printf("missing arr1[%d] -- %s\n",i,strerror(errno));
return 2;
}
}
printf("Enter integers\n");
for (int i = 0; i < A2MAX; i ) {
if (scanf("%d", &arr2[i]) != 1) {
printf("missing arr2[%d] -- %s\n",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 arr2\n");
else
printf("the minimum element in arr1 not in arr2 is: %d\n",min1);
return nomin;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/518355.html
標籤：数组C
下一篇：將字符陣列傳遞給函式會回傳警告