資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中陣列索引：左右兩側奇偶數計數相同
這裡我們將看到一個問題，假設給定一個數組，包含n個元素。我們需要找到一個索引，使得其左側偶數的頻率與右側偶數的頻率相同，或者其左側奇數的頻率與右側奇數的頻率相同。如果沒有這樣的結果，則返回-1。
假設陣列為{4, 3, 2, 1, 2, 4}。輸出為2。索引2處的元素為2，其左側只有一個奇數，右側也只有一個奇數。
為了解決這個問題，我們將建立兩個pair型別的向量來儲存左右兩側的資訊。左側的向量將儲存其左側奇數和偶數的頻率，右側的向量將對右側做同樣的操作。如果左側和右側的偶數計數相同，或者左側和右側的奇數計數相同，則返回該索引。
演算法
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
更新於：2019年8月20日
瀏覽量：101
廣告