ในปัญหานี้ เราได้รับอาร์เรย์ aar[] ของค่าจำนวนเต็ม n ค่าที่ไม่ได้เรียงลำดับและค่าจำนวนเต็ม งานของเราคือ ค้นหาดัชนีเริ่มต้นและจุดสิ้นสุดขององค์ประกอบในอาร์เรย์ที่ไม่เรียงลำดับ .
สำหรับการเกิดขึ้นขององค์ประกอบในอาร์เรย์ เราจะกลับมา
"ดัชนีเริ่มต้นและดัชนีสิ้นสุด " หากพบในอาร์เรย์สองครั้งขึ้นไป
"ดัชนีเดี่ยว หากพบในอาร์เรย์หนึ่งครั้ง
"ไม่มีองค์ประกอบ" หากไม่มีอยู่ในอาร์เรย์
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ตัวอย่างที่ 1
Input : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 2
Output : starting index = 0, ending index = 5 คำอธิบาย
ธาตุที่ ๒ มีอยู่ ๒ ประการ คือ
อันดับแรกที่ดัชนี =0,
ที่สองที่ดัชนี =5
ตัวอย่างที่ 2
Input : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 5
Output : Present only once at index 2 คำอธิบาย
มีองค์ประกอบ 5 เกิดขึ้นเพียงครั้งเดียวที่ดัชนี =2
ตัวอย่างที่ 3
Input : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 7
Output : Not present in the array! แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการสำรวจอาร์เรย์
เราจะสำรวจอาร์เรย์และเก็บค่าดัชนีไว้สองค่า ค่าแรกและค่าสุดท้าย ดัชนีแรกจะข้ามอาร์เรย์ตั้งแต่เริ่มต้น และดัชนีสุดท้ายจะข้ามอาร์เรย์จากจุดสิ้นสุด แล้วสิ้นสุดการวนซ้ำเมื่อค่าขององค์ประกอบที่ดัชนีแรกและดัชนีสุดท้ายเท่ากัน
อัลกอริทึม
-
ขั้นตอนที่ 1 − วนซ้ำอาร์เรย์
-
ขั้นตอนที่ 1.1 − ใช้ดัชนีแรกสำหรับการเดินทางจากจุดเริ่มต้นและดัชนีสุดท้ายสำหรับการเดินทางจากจุดสิ้นสุด
-
ขั้นตอนที่ 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
