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

Cho mảng n phần tử. Tìm chỉ mục nơi tần suất số chẵn bên trái = tần suất số chẵn bên phải, HOẶC tần suất số lẻ bên trái = tần suất số lẻ bên phải. Nếu không có, trả về -1.

Ví dụ mảng {4, 3, 2, 1, 2, 4}. Kết quả là 2. Phần tử tại chỉ mục 2 là 2, bên trái có 1 số lẻ, bên phải cũng có 1 số lẻ.

Giải pháp: tạo hai vector pair lưu thông tin trái/phải. Vector trái lưu tần suất lẻ/chẵn bên trái, vector phải làm tương tự cho bên phải. Nếu count chẵn hoặc count lẻ của hai bên bằng nhau, trả về chỉ mục.

Thuật toán

getIndex(arr, n) –

Bắt đầu
    odd = 0, even = 0
    left_vector, right_vector lưu pair (odd, even)
    thêm (odd, even) vào left_vector
    for i = 0 đến n-1:
        nếu arr[i] chẵn thì even++ ngược lại odd++
        thêm (odd, even) vào left_vector
    odd = 0, even = 0
    thêm (odd, even) vào right_vector
    for i = n-1 xuống 1:
        nếu arr[i] chẵn thì even++ ngược lại odd++
        thêm (odd, even) vào right_vector
    đảo ngược right_vector
    for mỗi phần tử tại chỉ mục i trong left_vector:
        nếu left_vector[i].first == right_vector[i].first HOẶC left_vector[i].second == right_vector[i].second
            trả về i
    trả về -1
Kết thúc

Ví dụ mã C++

#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++) { 
        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)); 
    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 << "chỉ mục: " << index; 
}

Kết quả

chỉ mục: 2