在C ++中两边的偶数或奇数计数相同的数组索引
在这里，我们将看到一个问题，假设给出了一个数组。有n个元素。我们必须找到一个索引，其左侧的偶数频率和右侧的偶数频率相同，或者其左侧的奇数频率与右侧的奇数频率相同。如果没有这样的结果，则返回-1。
假设数组像{4，3，2，1，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