c++ - 我如何为以特定数字开头和结尾的子集数量编写 O(n) 程序

Question

我们采用一个数组，其中每个索引都填充了一些数字。我们想从这个数组中找出以 3 开头并以 7 结尾的子集。

例如：

1,2,5,3,6,7,3,3,7,0,3,4,9,7,8

答案是 8，但我们不必打印出这些子集：

3,6,7
3,6,7,3,3,7
3,6,7,3,3,7,0,3,4,9,7
3,3,7
3,3,7,0,3,4,9,7
3,7
3,7,0,3,4,9,7
3,4,9,7

编码：

  int o_n_alg(int arr[], int size)
  {
    // To fill with O(n) Algorithm
  }

  int main(){
     int size = 1000000;
     int *array = new int[size];
     int ans_n;

     for (int i = 0; i < size; i++) 
       cin >> array[i];


     ans_n = o_n_alg(array, size);
  }

谁能帮助我如何填写int o_n_alg(int arr[], int size)功能？

标签： c++arraysalgorithmsearchtime-complexity

Answer 1

您可能会使用以下内容：

int o_n_alg(int arr[], int size)
{
    int result = 0;
    int count3 = 0;

    for (int i = 0; i != size; ++i) {
        if (arr[i] == 3) {
            ++count3;
        } else if (arr[i] == 7) {
            result += count3;
        }
    }
    return result;
}

结束7任何以前3的 .