在C ++中两边的偶数或奇数计数相同的数组索引

在这里,我们将看到一个问题,假设给出了一个数组。有n个元素。我们必须找到一个索引,其左侧的偶数频率和右侧的偶数频率相同,或者其左侧的奇数频率与右侧的奇数频率相同。如果没有这样的结果,则返回-1。

假设数组像{4,3,2,1,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

以上是 在C ++中两边的偶数或奇数计数相同的数组索引 的全部内容, 来源链接: utcz.com/z/327259.html

回到顶部