Chỉ mục mảng có cùng số lượng số chẵn hoặc lẻ ở cả hai bên trong C ++

Ở đây chúng ta sẽ thấy một vấn đề, giả sử một mảng được đưa ra. Có n phần tử. Chúng ta phải tìm một chỉ số, trong đó tần số của các số chẵn ở bên trái và tần số của các số chẵn ở bên phải của nó bằng nhau, hoặc tần số của các số lẻ bên trái của nó bằng tần số của các số lẻ bên phải của nó. Nếu không có kết quả như vậy, trả về -1.

Giả sử mảng giống như {4, 3, 2, 1, 2, 4}. Kết quả là 2. Phần tử ở chỉ mục 2 là 2, chỉ có một số lẻ ở bên trái của nó và cũng chỉ có một số lẻ ở bên phải của nó.

Để giải quyết vấn đề này, chúng ta sẽ tạo hai cặp vectơ để lưu trữ thông tin trái và phải. vectơ cho bên trái sẽ lưu trữ tần số của các số lẻ và số chẵn ở phía bên trái của nó, và vectơ cho bên phải sẽ làm tương tự đối với phía bên phải. Nếu số chẵn cho trái và phải hoặc số lẻ cho trái và phải là như nhau, thì trả về chỉ mục.

Thuật toán

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

Ví dụ

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

Đầu ra

index : 2