在C ++中找到具有正好为k个奇数的最长子数组

  • Z时代
  • 2024-01-10
  • 分类：综合

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

我们可以使用滑动窗口解决此问题。任务如下-

  • 初始化max：= 0，count：= 0和start：= 0

  • 对于介于0到n – 1之间的i，请执行以下操作

    • 如果max <（i –开始+1），则max：=（i –开始+1）

    • 如果arr [start] mod 2不为0，则将count减1

    • 开始增加1

    • 如果arr [i] mod 2不为0，则将count增加1

    • 当count> k并开始<= i时，请执行以下操作

    • 如果count = k，则

    • 返回最大值

    示例

    #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

    以上是 在C ++中找到具有正好为k个奇数的最长子数组 的全部内容， 来源链接： utcz.com/z/322151.html

    回到顶部