หาดัชนีเริ่มต้นและสิ้นสุดของสมาชิกในอาร์เรย์ที่ไม่ได้เรียงลำดับใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n จำนวนเต็มที่ไม่ได้เรียงลำดับ และจำนวนเต็ม val งานของเราคือ การหาดัชนีเริ่มต้นและสิ้นสุดของสมาชิกในอาร์เรย์ที่ไม่ได้เรียงลำดับ

สำหรับการปรากฏของสมาชิกในอาร์เรย์ เราจะคืนค่า:

• "Starting index and ending index" หากพบในอาร์เรย์ 2 ครั้งขึ้นไป
• "Single index" หากพบในอาร์เรย์เพียง 1 ครั้ง
• "Element not present" หากไม่ได้อยู่ในอาร์เรย์

ตัวอย่างที่ 1

Input : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 2 
Output : starting index = 0, ending index = 5

คำอธิบาย

มีการปรากฏของสมาชิก 2 ทั้งหมด 2 ครั้ง
ครั้งแรกที่ index = 0
ครั้งที่สองที่ index = 5

ตัวอย่างที่ 2

Input : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 5 
Output : Present only once at index 2

คำอธิบาย

มีการปรากฏของสมาชิก 5 เพียง 1 ครั้ง ที่ index = 2

ตัวอย่างที่ 3

Input : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 7 
Output : Not present in the array!

แนวทางแก้ปัญหา

วิธีแก้ที่ง่ายคือการเดินผ่านอาร์เรย์ เราจะใช้ดัชนี 2 ตัว คือ first (เริ่มจากหน้า) และ last (เริ่มจากท้าย) เดินเข้าหากันจนกว่าทั้งคู่จะเจอค่าที่ต้องการหรือพบกัน

อัลกอริทึม

• ขั้นตอนที่ 1 − วนลูปผ่านอาร์เรย์
  • ขั้นตอนที่ 1.1 − ใช้ first index เดินจากหน้า และ last index เดินจากท้าย
  • ขั้นตอนที่ 1.2 − หากค่าที่ดัชนีใดเท่ากับ val ให้หยุดเพิ่มดัชนีนั้น
  • ขั้นตอนที่ 1.3 − หากค่าทั้งสองดัชนีเท่ากัน (เจอค่าเดียวกัน) ให้หยุด

ตัวอย่างโค้ด

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

ผลลัพธ์

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