หาดัชนีอาร์เรย์ที่จำนวนเลขคู่/คี่เท่ากันทั้งสองข้างใน C++

ที่นี่เราจะดูปัญหาหนึ่ง สมมติมีอาร์เรย์หนึ่ง มี n องค์ประกอบ เราต้องหาดัชนีหนึ่ง ที่ความถี่ของเลขคู่ทางซ้าย และความถี่ของเลขคู่ทางขวาเท่ากัน หรือความถี่ของเลขคี่ทางซ้ายเท่ากับความถี่ของเลขคี่ทางขวา หากไม่มีผลลัพธ์ ให้ส่งคืน -1

สมมติอาร์เรย์เป็น {4, 3, 2, 1, 2, 4} ผลลัพธ์คือ 2 องค์ประกอบที่ดัชนี 2 คือ 2 มีเลขคี่เพียง 1 ตัวทางซ้าย และทางขวาก็มีเลขคี่เพียง 1 ตัว

เพื่อแก้ปัญหานี้ เราจะสร้างสองเวกเตอร์ของคู่ (pairs) เพื่อเก็บข้อมูลซ้ายและขวา เวกเตอร์ซ้ายจะเก็บความถี่ของเลขคี่และคู่ทางซ้าย และเวกเตอร์ขวาทำอย่างเดียวกันสำหรับขวา หากจำนวนคู่ซ้าย-ขวาหรือจำนวนคี่ซ้าย-ขวาเท่ากัน ให้ส่งคืนดัชนีนั้น

อัลกอริทึม

getIndex(arr, n):

Begin
    กำหนด odd และ even เริ่มต้นเป็น 0
    กำหนด left_vector, right_vector สำหรับคู่ odd-even
    เพิ่ม (odd, even) เข้า left_vector
    for i ในช่วง 0 ถึง n-1:
        ถ้า arr[i] เป็นเลขคู่ เพิ่ม even มิฉะนั้นเพิ่ม odd
        เพิ่ม (odd, even) เข้า left_vector
    done
    odd := 0 และ even := 0
    เพิ่ม (odd, even) เข้า right_vector
    for i ในช่วง n-1 ลงถึง 1:
        ถ้า arr[i] เป็นเลขคู่ เพิ่ม even มิฉะนั้นเพิ่ม odd
        เพิ่ม (odd, even) เข้า right_vector
    done
    reverse right_vector
    for แต่ละองค์ประกอบที่ดัชนี i ใน left_vector:
        ถ้า left_vector[i].first == right_vector[i].first หรือ left_vector[i].second == right_vector[i].second ส่งคืน i
    done
    ส่งคืน -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++) {
        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 << "index: " << index;
    }
}

ผลลัพธ์

index: 2