이 문제에서는 정렬되지 않은 n개의 정수 값과 정수 val의 배열 aar[]가 제공됩니다. 우리의 임무는 정렬되지 않은 배열에서 요소의 시작 및 끝 인덱스를 찾는 것입니다. .
배열에서 요소가 발생하면 다음을 반환합니다.
"시작 색인과 끝 색인 " 배열에서 두 번 이상 발견된 경우.
"단일 색인" 배열에서 한 번 발견된 경우.
"요소가 없습니다" 배열에 없는 경우.
문제를 이해하기 위해 예를 들어 보겠습니다.
예시 1
Input : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 2
Output : starting index = 0, ending index = 5 설명
요소 2가 두 번 발생합니다.
먼저 인덱스 =0에서
인덱스에서 두 번째 =5
예시 2
Input : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 5
Output : Present only once at index 2 설명
인덱스 =2에서 요소 5가 한 번만 나타납니다.
예시 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