查找具有指定数量的奇数整数的子数组的数量 [英] find number of subarrays with specified number of odd integers

问题描述

给出一个整数数组和一个整数m，如何查找包含m个奇数整数的所有子数组?如果是我的还不够，下面是完整问题的详细说明.有没有比n ^ 2更快的解决方案?我下面的解决方案似乎是n ^ 2，我不确定如何进一步优化它.

Given an array of integers and an integer m, how can I find all subarrays that contain m odd integers? Below is a longer description of the full problem if mine is not sufficient. Is there a solution to this problem that is faster than n^2? My solution below appears to be n^2 and I am unsure about how to further optimize it.

https://github.com/cem3394/HR-Haskell/blob/master/beautifulSubarrays.hs

    static long beautifulSubarrays(int[] a, int m) {
    int sum = 0;
    for (int i = 0; i < a.length; i++){
        for (int j = i, c =0; j < a.length; j++){
            if (a[j] %2 !=0){
                c++;
            }
            if ((c==m) && (z==j)){
                over = true;
                sum++;
                break
            }
            boolean over = false;
            if (over) break;
            for (int z = i, c = 0; z <= j; z++){
                if (a[z]%2 != 0){
                    c++;

                }
                if (c>m){
                    over = true;
                    break;

                }
                if ((c==m) && (z==j)){
                    over = true;
                    sum++;
                    break;
                }
            }
        }
    }
    return sum;


    }

推荐答案

这是两指针方法的任务.

This is task for two-pointer approach.

制作两个索引-L和R.

Make two indexes - L and R.

将L设置为0，并将R从0移到右侧，在Od计数器中计数奇数.当Od变为m时，将R位置记为R0.进一步移动R直到满足新的奇数.

Set L to 0 and move R from 0 to the right, counting odd numbers in Od counter. When Od becomes m, remember R position as R0. Move R further until new odd number is met.

将L位置记住为L0，并递增L直到满足奇数为止(如果A [L0]为奇数，则保持该状态).

Remember L position as L0 and increment L until odd number is met (stay if A[L0] is odd).

现在，所有以L0..L范围开始且以R0..R-1范围结束的子数组都包含正好m个奇数.有Cnt = (L-L0+1) * (R-R0)这样的子数组:

Now all sub-arrays starting in L0..L range and ending in R0..R-1 range, contain exactly m odd numbers. There are Cnt = (L-L0+1) * (R-R0) such sub-arrays:

m=3 
       L0 L        R0           R
i      0  1  2  3  4  5  6  7  8 
A[i]   4  1  3  2  5  6  2  2  3

所有以0..1开始并以4..7结尾的子数组都包含3个奇数，这里有2个索引用于开始，4个索引用于结束，因此Cnt = 8

all sub-arrays starting in 0..1 and ending in 4..7, contain 3 odd numbers, here are 2 indexes for start and 4 indexes for end, so Cnt = 8

递增L，请记住R0，再次重复此过程直到数组结束，并为结果的每个范围添加Cnt

Increment L, remember R0 again an repeat this procedure until array end, adding Cnt for every range set to the result

指针仅遍历数组一次，复杂度是线性的.

Pointers traverse array only once, complexity is linear.

这篇关于查找具有指定数量的奇数整数的子数组的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！