Trong bài toán này, chúng ta được cung cấp hai mảng đã sắp xếp arr1 và arr2 có kích thước n và n + 1 với tất cả các phần tử giống nhau ngoại trừ phần tử thừa. Nhiệm vụ của chúng tôi là tìm chỉ mục của một phần tử bổ sung có trong một mảng đã sắp xếp .
Mô tả sự cố: Chúng ta cần tìm chỉ số của một phần tử từ mảng kích thước n + 1 mà không có trong mảng kích thước n.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào: arr1 [n] ={3, 5, 7, 8, 9, 12}
arr2 [n + 1] ={3, 4, 5, 7, 8, 9, 12}
Đầu ra: 1
Giải thích:
Phần tử có giá trị 4 là phần tử phụ ở chỉ số 1.
Phương pháp tiếp cận Giải pháp -
Một giải pháp đơn giản cho vấn đề là sử dụng thực tế là cả hai mảng đều được sắp xếp. Và chỉ với một phần tử không bằng nhau, chúng ta có thể thực hiện tìm kiếm tuyến tính và tìm phần tử trong arr2 mà không có trong arr1 [].
Thuật toán:
Bước 1: Vòng lặp cho i -> 0 đến n + 1,
Bước 1.1: tìm các phần tử lẻ, nếu arr1 [i]! =arr2 [i], vòng lặp ngắt.
Bước 2: trả về giá trị của i.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <iostream>
using namespace std;
int findExtraElement(int arr1[], int arr2[], int n) {
int i;
for (i = 0; i < n; i++)
if (arr1[i] != arr2[i])
break;
return i;
}
int main()
{
int arr1[] = {3, 5, 7, 8, 9, 12};
int arr2[] = {3, 4, 5, 7, 8, 9, 12};
int n = sizeof(arr1) / sizeof(arr1[0]);
int extraIndex = findExtraElement(arr1, arr2, n);
cout<<"The extra element is at index ("<<extraIndex<<") and the value is "<<arr2[extraIndex];
return 0;
} Đầu ra
The extra element is at index (1) and the value is 4
Giải pháp này có thể được thực hiện tốt hơn bằng cách sử dụng kỹ thuật tìm kiếm hiệu quả hơn là tìm kiếm nhị phân thay vì giảm tuyến tính thời gian tính toán của thuật toán:
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <iostream>
using namespace std;
int findExtraElement(int arr1[], int arr2[], int n) {
int extraIndex = n;
int start = 0, end = n - 1;
while (start <= end)
{
int mid = (start + end) / 2;
if (arr2[mid] == arr1[mid])
start = mid + 1;
else
{
extraIndex = mid;
end = mid - 1;
}
}
return extraIndex;
}
int main()
{
int arr1[] = {3, 5, 7, 8, 9, 12};
int arr2[] = {3, 4, 5, 7, 8, 9, 12};
int n = sizeof(arr1) / sizeof(arr1[0]);
int extraIndex = findExtraElement(arr1, arr2, n);
cout<<"The extra element is at index ("<<extraIndex<<") and the value is "<<arr2[extraIndex];
return 0;
} Đầu ra
The extra element is at index (1) and the value is 4
Cách tiếp cận khác:
Một cách tiếp cận khác để giải quyết vấn đề là tìm sự khác biệt tuyệt đối giữa hai mảng, đó là phần tử phụ. Sau đó, chúng ta cần tìm chỉ số của phần tử phụ này trong mảng có kích thước n + 1. Điều này có thể được thực hiện bằng cách sử dụng một thuật toán tìm kiếm.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <iostream>
using namespace std;
int calcArraysum(int arr[], int n){
int sum = 0;
for(int i = 0; i < n; i++)
sum += arr[i];
return sum;
}
int findExtraElement(int arr1[], int arr2[], int n) {
int extraValue = calcArraysum(arr2, n+1) - calcArraysum(arr1, n);
for (int i = 0; i < n; i++)
{
if (arr2[i] == extraValue)
return i;
}
return -1;
}
int main()
{
int arr1[] = {3, 5, 7, 8, 9, 12};
int arr2[] = {3, 4, 5, 7, 8, 9, 12};
int n = sizeof(arr1) / sizeof(arr1[0]);
int extraIndex = findExtraElement(arr1, arr2, n);
cout<<"The extra element is at index ("<<extraIndex<<") and the value is "<<arr2[extraIndex];
return 0;
} Đầu ra
The extra element is at index (1) and the value is 4