ที่นี่เราจะเห็นปัญหาหนึ่ง สมมติว่ามีหนึ่งอาร์เรย์ มี 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
