在 C++ 中查找具有恰好 k 个奇数的最长子数组

假设我们有一个包含 n 个元素的数组。问题是找到具有恰好 k 个奇数的最长子数组。因此，如果 A = [2, 3, 4, 11, 4, 12, 7]，并且 k = 1，则输出将为 4，子数组为 [4, 11, 4, 12]

我们可以使用滑动窗口来解决这个问题。任务如下所示：

  • 初始化 max := 0，count := 0，以及 start := 0
  • 对于 i 从 0 到 n – 1 的范围，执行以下操作
    • 如果 arr[i] 模 2 不为 0，则将 count 加 1
    • 当 count > k 且 start <= i 时，执行以下操作
      • 如果 arr[start] 模 2 不为 0，则将 count 减 1
      • 将 start 加 1
    • 如果 count = k，则
      • 如果 max < (i – start + 1)，则 max := (i – start + 1)
    • 返回 max

示例

 在线演示

#include<iostream>
using namespace std;
int oddSubarrayMaxLength(int arr[], int n, int k) {
   int max_len = 0, count = 0, start = 0;
   for (int i = 0; i < n; i++) {
      if (arr[i] % 2 != 0)
         count++;
      while (count > k && start <= i)
         if (arr[start++] % 2 != 0)
            count--;
      if (count == k)
      if (max_len < (i - start + 1))
      max_len = i - start + 1;
   }
   return max_len;
}
int main() {
   int arr[] = {2, 3, 4, 11, 4, 12, 7};
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 1;
   cout << "Maximum Length is: "<< oddSubarrayMaxLength(arr, n, k);
}

输出

Maximum Length is: 4

更新于: 2019-12-18

63 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告