小编典典

每个词的出现次数

algorithm

我给了一个数组a[n][2],最大n可以10^5在哪里。有n个科目和n个学生。全部编号为1、2,…,n。

a[i][0]a[i][1]1 <= i <= n)分别表示,在第i个主题,从学生a[i][0]a[i][1]通过,而其余没有。我应该找到每个学生通过的科目数量。

例如

n=5 and a = [ [1,3], [1,3], [1,5], [1,5], [1,5] ]

应该输出

[5, 5, 5, 3, 3]

(2)

n = 10, a = [ [1,10], [1,10], [1,10], [3,5], [1,10], ..., [1,10] ]

预期答案应该是

[ 9, 9, 10, 10, 10, 9, 9, 9, 9, 9]

阅读 233

收藏
2020-07-28

共1个答案

小编典典

不太了解您的代码,这是另一种方法。这类似于间隔问题。让我们举个例子:

  • n = 5
  • a = [[1,3],[1,3],[1,5],[1,5],[1,5]]

我们首先将大小数组设为no。的主题数+ 1(为简化计算)。

1   2   3   4   5   6
  • 现在,让我们一个接一个地进行检查。每当遇到间隔时,我们都会+1在起点和-1终点加上第 1 个位置。

数组表示形式:( 在上述整个过程之后)。

 1          2          3          4         5         6

+1                               -1                           [1,3]
+1                               -1                           [1,3]
+1                                                   -1       [1,5]
+1                                                   -1       [1,5]
+1                                                   -1       [1,5]
  • 所有未决的事情只是从左到右开始求和,您将为每个学生得到答案。上面的过程之所以有效,是因为我们在每个间隔的最后一个学生之后否定了(如-1一样),因为其他学生没有通过该特定主题。因此,求和时,我们一定会为每个学生得到正确的总数。

汇总如下:

 1          2          3          4         5         6

+1                               -1                           [1,3]
+1                               -1                           [1,3]
+1                                                   -1       [1,5]
+1                                                   -1       [1,5]
+1                                                   -1       [1,5]

 5          5          5          3         3         0(not considered anyway)
2020-07-28