Trong bài toán này, chúng ta được cung cấp một mảng aar [] gồm n giá trị nguyên không được sắp xếp và một số nguyên val. Nhiệm vụ của chúng tôi là tìm chỉ số bắt đầu và kết thúc của một phần tử trong một mảng không được sắp xếp .
Đối với sự xuất hiện của phần tử trong mảng, chúng tôi sẽ trả về,
"Chỉ mục bắt đầu và chỉ mục kết thúc" nếu nó được tìm thấy trong mảng hai lần trở lên.
"Chỉ mục duy nhất" nếu nó được tìm thấy trong mảng một lần.
"Phần tử không có mặt" nếu nó không có trong mảng.
Hãy lấy một ví dụ để hiểu vấn đề,
Ví dụ 1
Input : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 2
Output : starting index = 0, ending index = 5 Giải thích
Có hai lần xuất hiện của phần tử 2,
Đầu tiên ở chỉ mục =0,
Đứng thứ hai ở chỉ số =5
Ví dụ 2
Input : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 5
Output : Present only once at index 2 Giải thích
Chỉ có một lần xuất hiện của phần tử 5, tại index =2,
Ví dụ 3
Input : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 7
Output : Not present in the array! 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à duyệt qua mảng.
Chúng tôi sẽ duyệt qua mảng và giữ hai giá trị chỉ mục, đầu tiên và cuối cùng. Chỉ mục đầu tiên sẽ đi qua mảng từ đầu và chỉ mục cuối cùng sẽ đi qua mảng từ cuối. Và sau đó kết thúc vòng lặp khi giá trị của phần tử ở chỉ mục đầu tiên và chỉ số cuối cùng trở nên giống nhau.
Thuật toán
-
Bước 1 - Lặp qua mảng
-
Bước 1.1 - Sử dụng chỉ mục đầu tiên để duyệt từ đầu và chỉ mục cuối cùng để duyệt từ cuối.
-
Bước 1.2 - nếu giá trị tại bất kỳ chỉ mục nào bằng val. Không tăng giá trị chỉ mục.
-
Bước 1.3 - nếu cả hai giá trị ở cả hai chỉ mục đều trả về như nhau.
-
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#include <iostream>
using namespace std;
void findStartAndEndIndex(int arr[], int n, int val) {
int start = 0;
int end = n -1 ;
while(1){
if(arr[start] != val)
start++;
if(arr[end] != val)
end--;
if(arr[start] == arr[end] && arr[start] == val)
break;
if(start == end)
break;
}
if (start == end ){
if(arr[start] == val)
cout<<"Element is present only once at index : "<<start;
else
cout<<"Element Not Present in the array";
} else {
cout<<"Element present twice at \n";
cout<<"Start index: "<<start<<endl;
cout<<"Last index: "<<end;
}
}
int main() {
int arr[] = { 2, 1, 5, 4, 6, 2, 9, 0, 2, 3, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int val = 2;
findStartAndEndIndex(arr, n, val);
return 0;
} Đầu ra
Element present twice at Start index: 0 Last index: 8