여기서 우리는 하나의 배열이 주어진다고 가정할 때 하나의 문제를 보게 될 것입니다. n개의 요소가 있습니다. 왼쪽의 짝수의 빈도와 오른쪽의 짝수의 빈도가 같거나 왼쪽의 홀수의 빈도와 오른쪽의 홀수의 빈도가 같은 하나의 인덱스를 찾아야 합니다. 그러한 결과가 없으면 -1을 반환합니다.
배열이 {4, 3, 2, 1, 2, 4}와 같다고 가정합니다. 출력은 2입니다. 인덱스 2의 요소는 2이고 왼쪽에 홀수가 하나만 있고 오른쪽에도 홀수가 하나만 있습니다.
이 문제를 해결하기 위해 왼쪽 및 오른쪽 정보를 저장할 두 쌍의 벡터를 생성합니다. 왼쪽에 대한 벡터는 왼쪽의 홀수 및 짝수의 빈도를 저장하고 오른쪽에 대한 벡터는 오른쪽에 대해 동일한 작업을 수행합니다. 왼쪽과 오른쪽의 짝수 개수 또는 왼쪽과 오른쪽의 홀수 개수가 같으면 인덱스를 반환합니다.
알고리즘
getIndex(arr, n) -
Begin define odd and even, and initialize as 0 define left_vector, right_vector for odd even pairs add (odd, even) into left_vector for i in range 0 to n-1, do if arr[i] is even, then increase even, otherwise increase odd add (odd, even) into left_vector done odd := 0 and even := 0 add (odd, even) into right_vector for i in range n-1 down to 1, do if arr[i] is even, then increase even, otherwise increase odd add (odd, even) into right_vector done reverse the right_vector for each element at index i in left_vector, do if left_vector[i].first = right_vector[i].first, or left_vector[i].odd= right_vector[i].odd, then return i done return -1 End
예시
#include <iostream> #include <vector> #include <utility> #include <algorithm> using namespace std; int getIndex(int n, int arr[]) { int odd = 0, even = 0; vector<pair<int, int >> left_vector, right_vector; left_vector.push_back(make_pair(odd, even)); for (int i = 0; i < n - 1; i++) { //count and store odd and even frequency for left side if (arr[i] % 2 == 0) even++; else odd++; left_vector.push_back(make_pair(odd, even)); } odd = 0, even = 0; right_vector.push_back(make_pair(odd, even)); //count and store odd and even frequency for right side for (int i = n - 1; i > 0; i--) { if (arr[i] % 2 == 0) even++; else odd++; right_vector.push_back(make_pair(odd, even)); } reverse(right_vector.begin(), right_vector.end()); for (int i = 0; i < left_vector.size(); i++) { if (left_vector[i].first == right_vector[i].first || left_vector[i].second == right_vector[i].second) return i; } return -1; } int main() { int arr[] = {4, 3, 2, 1, 2}; int n = sizeof(arr) / sizeof(arr[0]); int index = getIndex(n, arr); if(index == -1) { cout << "-1"; } else { cout << "index : " << index; } }
출력
index : 2