Tìm chỉ số bắt đầu và kết thúc của phần tử trong mảng không sắp xếp trong C++

Trong bài toán này, chúng ta được cho 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 ta là tìm chỉ số bắt đầu và kết thúc của một phần tử trong mảng không sắp xếp.

Đối với sự xuất hiện của phần tử trong mảng, ta sẽ trả về:

"Chỉ số bắt đầu và kết thúc" nếu tìm thấy trong mảng hai lần trở lên.

"Chỉ số đơn lẻ" nếu tìm thấy trong mảng một lần.

"Phần tử không có mặt" nếu không có trong mảng.

Hãy xem ví dụ sau để hiểu bài toá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,
Lần đầu tại chỉ số = 0,
Lần thứ hai tại 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 chỉ số = 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 giải

Một giải pháp đơn giản là duyệt mảng.

Ta sẽ duyệt mảng và giữ hai giá trị chỉ số, first và last. Chỉ số first duyệt từ đầu và last duyệt từ cuối. Sau đó kết thúc vòng lặp khi giá trị phần tử tại first và last trở nên giống nhau.

Thuật toán

• Bước 1 − Lặp qua mảng

  • Bước 1.1 − Dùng first để duyệt từ đầu và last để duyệt từ cuối.

  • Bước 1.2 − Nếu giá trị tại bất kỳ chỉ số nào bằng val. Không tăng giá trị chỉ số.

  • Bước 1.3 − Nếu cả hai giá trị tại hai chỉ số giống nhau thì trả về.

Ví dụ

Chương trình minh họa cho giải pháp

#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; }

Kết quả

Element present twice at Start index: 0 Last index: 8