Sử dụng toán tử XOR để tìm các phần tử trùng lặp trong một mảng không thành công trong nhiều trường hợp

Question

Tôi gặp một bài đăng How to find a duplicate element in an array of shuffled consecutive integers? nhưng sau đó nhận ra rằng điều này không thành công đối với nhiều đầu vào.

Đối với ví dụ:
arr[] = {601,602,603,604,605,605,606,607}

#include <stdio.h> 
int main() 
{ 
int arr[] = {2,3,4,5,5,7}; 
int i, dupe = 0; 
for (i = 0; i < 6; i++) { 
    dupe = dupe^a[i]^i; 
} 
printf ("%d\n", dupe); 
return 0; 
} 

Làm thế nào tôi có thể sửa đổi mã này để các yếu tố trùng lặp có thể được tìm thấy cho tất cả các trường hợp?

Answer 1

Từ câu hỏi ban đầu:

Giả sử bạn có một mảng của 1001 số nguyên. Các số nguyên theo thứ tự ngẫu nhiên, nhưng bạn biết từng số nguyên nằm trong khoảng từ 1 đến 1000 (bao gồm). Ngoài ra, mỗi số chỉ xuất hiện một lần trong mảng, ngoại trừ một số, xuất hiện hai lần.

Nó về cơ bản nói, thuật toán mà chỉ có tác dụng khi bạn có số nguyên liên tiếp, bắt đầu với 1, kết thúc với một số N.

Nếu bạn muốn thay đổi nó cho trường hợp tổng quát hơn, bạn phải làm những điều sau:

Tìm tối thiểu và tối đa trong mảng. Sau đó tính toán đầu ra mong đợi (xor tất cả các số nguyên giữa tối thiểu và tối đa). Sau đó tính toán xor của tất cả các phần tử trong mảng. Sau đó xor này hai điều và bạn sẽ có được một đầu ra.

Answer 2

Đây là mã được hiển thị trong câu hỏi gốc, khác với việc triển khai của bạn. Bạn đã sửa đổi nó để sử dụng một biến địa phương thay vì thành viên cuối cùng của mảng, mà làm cho một sự khác biệt:

for (int i = 1; i < 1001; i++) 
{ 
    array[i] = array[i]^array[i-1]^i; 
} 

printf("Answer : %d\n", array[1000]); 

Answer 3

Tuyên bố XOR có thuộc tính 'a' XOR 'a' sẽ luôn là 0, nghĩa là chúng hủy, vì vậy, nếu bạn biết rằng danh sách của bạn chỉ có một bản sao và phạm vi đó là x thành y , 601 đến 607 trong trường hợp của bạn, có khả năng giữ xor của tất cả các phần tử từ x thành y trong một biến, và sau đó xor biến này với tất cả các phần tử bạn có trong mảng của bạn. Vì sẽ chỉ có một phần tử sẽ được nhân đôi nó sẽ không bị hủy bỏ do hoạt động xor và đó sẽ là câu trả lời của bạn.

void main() 
{ 
    int a[8]={601,602,603,604,605,605,606,607}; 
    int k,i,j=601; 

    for(i=602;i<=607;i++) 
    { 
     j=j^i; 
    } 

    for(k=0;k<8;k++) 
    { 
     j=j^a[k]; 
    } 

    printf("%d",j); 
} 

Mã này sẽ cho đầu ra 605, như mong muốn!

Answer 4

//There i have created the program to find out the duplicate element in array. Please edit if there are required some changes. 
int main() 
{ 
    int arr[] = {601,602,603,604,605,605,606,607}; 
    //int arr[] = {601,601,604,602,605,606,607}; 
    int n= sizeof(arr)/sizeof(arr[0]); 

    for (int i = 0; i < n; i++) 
    { 
     for (int j = i+1; j < n; j++) 
     { 
      int res = arr[i]^arr[j]; 

      if (res == 0) 
      { 
       std::cout<< "Repeated Element in array = "<<arr[i]<<std::endl; 
      } 
     } 
    } 
    return 0; 
} 

// HOẶC Bạn có thể sử dụng Hashtable và hàm Hash khi bạn nhập vào cùng một giá trị
vào bảng băm thời gian mà bạn có thể làm cho số lượng lớn hơn nếu
một giá trị của nó ở chỉ số cụ thể của HashTable sau đó bạn có thể nói rằng có giá trị lặp lại trong mảng.