로직 도움말 (C)

Question

두 개의 비 반복 시퀀스 (배열)에서 첫 번째 n 요소를 교환해야합니다. 여기서 n은 임의의 정수입니다.

Seq1 1 4 5 6 7 8 9 1 2 3 7

Seq2 3 9 8 7 1 2 3 4 5 6

만약 N = 4

Seq1 : 9 3 1 2 | 9 8 2 3 7

Seq2 : 1 4 5 6 | 8 7 4 5 6

이제 '|'다음에 반복되는 숫자를 교체하여 시퀀스를 복구해야합니다.

어떻게 하시겠습니까? 처음 n 요소를 스와핑

이 내 노력입니다 ..

for(left1 = 0; left1<pivot; left1++) 
    { 
    for(right1 = pivot; right1 < no_jobs; right1++) 
    { 
    if(S1->sequence[left1] == S1->sequence[right1]) 
     { 
     for(left2 = 0; left2<pivot; left2++) 
     { 
      for(right2 = pivot; right2<no_jobs; right2++) 
      { 
      if(S2->sequence[left2] == S2->sequence[right2]) 
      { 
       swap_temp = S1->sequence[right1]; 
       S1->sequence[right1] = S2->sequence[right2]; 
       S2->sequence[right2] = swap_temp; 
       break; 
      } 
      } 
     } 
     } 
    } 
    } 

Answer 1

는 루프 하나를 사용하여 간단합니다.

for(int i = 0; i < n; i++){ 
    int tmp = array1[i]; 
    array1[i] = array2[i]; 
    array2[i] = tmp; 
} 

이제 배열에서 변경된 사항을 찾아야합니다. 스왑 한 부품을 비교하여이 작업을 수행 할 수 있습니다.

int m1 = 0, m2 = 0; 
int missing_array1[n]; 
int missing_array2[n]; 

for(int i = 0; i < n; i++){ 
    bool found = false; 
    for(int j = 0; j < n; j++){ 
     if(array1[i] == array2[j]){ 
      found = true; 
      break; 
     } 
    } 
    if(!found){ 
     missing_array2[m2++] = array1[i]; 
    } 
} 

for(int i = 0; i < n; i++){ 
    bool found = false; 
    for(int j = 0; j < n; j++){ 
     if(array2[i] == array1[j]){ 
      found = true; 
      break; 
     } 
    } 
    if(!found){ 
     missing_array1[m1++] = array2[i]; 
    } 
} 

missing_array2에는 이제 array2에서 누락 된 숫자가 포함됩니다. 이것들은 모두 array1에 복사 될 모든 숫자입니다. missing_array1도 마찬가지입니다. 다음으로 두 배열을 모두 스캔하고 누락 된 숫자로 중복을 대체해야합니다.

while(m1 >= 0){ 
    int z = 0; 
    while(missing_array1[m1] != array2[n + z]){ 
     z++; 
    } 
    array2[n + z] = missing_array2[m1--]; 
} 

while(m2 >= 0){ 
    int z = 0; 
    while(missing_array2[m2] != array1[n + z]){ 
     z++; 
    } 
    array1[n + z] = missing_array1[m2--]; 
} 

요약하면 스왑 한 부분을 비교하여 각 배열에서 누락 될 값을 찾습니다. 이 값은 반대 배열에 복제되는 값이기도합니다. 그런 다음 각 배열을 스캔하여 누락 된 값 중 하나를 사용하여 중복 값을 대체합니다 (모든 값이 고유 한 경우 누락 된 값을 신경 쓰지 않는다고 가정)

Answer 2

스왑 된 부분이 시퀀스에 같은 값이 들어 있으면 반복이 없으므로 스왑을 수행하면 첫 번째 n 개 요소가 섞일 수 있습니다. 따라서 복구해야하는 값은 교체 된 시퀀스 중 하나에서 발생하는 값입니다.

시퀀스 1의 비트를 비트 0으로 계산하고 시퀀스 2의 비트를 비트 1로 사용하여 스왑 된 n 개의 요소의 히스토그램을 작성합니다. 히스토그램의 구성원이 0이 아닌 경우 하나 또는 다른 시퀀스에서 발생합니다 only.

복구가 필요한 값이있는 경우 재 작성이 필요한 값의 찾아보기 테이블을 구성 할 수 있습니다. 히스토그램의 비대칭 값 중 하나가 아니라면 다른 비대칭 값으로 매핑해야합니다.

Seq1: 1 4 5 6 9 8 2 3 7 

Seq2: 3 9 1 2 8 7 4 5 6 

만약 N = 4

Seq1: 3 9 1 2 | 9 8 2 3 7 

Seq2: 1 4 5 6 | 8 7 4 5 6 

히스토그램

value 1 2 3 4 5 6 7 8 9 
count 3 1 1 2 2 2 0 0 1 

히스토그램 [S1은 [내가] & 1로 [I]가 S1]을 교체하면서 서열 1 (대 매핑 S2 [i])

value 1 2 3 4 5 6 7 8 9 
replace 1 6 5 4 5 6 7 8 4 

매핑 I 1 시퀀스> N 서열 2

Seq1: 3 9 1 2 | 9 8 2 3 7 
replace - - - - | 4 8 6 5 7 
result 3 9 1 2 | 4 8 6 5 7 

매핑 (히스토그램 [S2는 [내가] & 2 대체하면서 S2를 [I]과 S1 [I])

value 1 2 3 4 5 6 7 8 9 
replace 1 2 3 9 3 2 7 8 9 

매핑 I 1 시퀀스에 적용> N

Seq2: 1 4 5 6 | 8 7 4 5 6 
replace - - - - | 8 7 9 3 2 
result 1 4 5 6 | 8 7 9 3 2 

다르게는, 히스토그램 (은 반복되는도 자체의 값을 교체를 확인할 필요가 교환)에 설정되어있는 다른 비트와 다음의 값으로 대체; 결과의 값이 유일한 경우 대체 값으로 사용되는 값이 실제로 중요하지 않다고 가정합니다.