减少时间复杂度从n平方

Question

减少时间复杂度从n平方

3

班级里有 n 名学生。即将到来的跨校科学竞赛中，将出现4个学科的问题，为简单起见，称其为1,2,3和4。每个学生在某个学科上表现优秀或糟糕的概率相等。

我们获得了n行输入，每行有4个条目。如果第i列等于1，则表示该学生在第i个学科上表现良好。我需要找出学校可以派遣多少支队伍，以便两名学生共同掌握所有4个学科。

例如：

S1: 1 1 1 1
S2: 1 1 0 1
S3: 1 0 1 1
S4: 0 0 1 1
S5: 0 0 0 0

学生1可以和任何一位学生一起，因为所有科目都是他的强项。 => 4

学生2可以与S3和S4一起，因为S2擅长科目1、2和4，而S3和S4擅长科目3。 => 2（注意已经计算了（S1，S2））

S3将与擅长科目2的人一起去=>无法匹配

S4：同样没有匹配。

因此，ans=4+2=6

我的解决方案：

ans=0;
//arr is the array containing subject-wise "strength" of students
for(int i=0;i<n;i++){
    ArrayList<Integer> a=new ArrayList<>();
    for(int j=0;j<4;j++)
        if(arr[i][j]==0)
            a.add(j);
    if(a.size()==0)
        ans+=n-i-1;
    else
        for(int j=i+1;j<n;j++){
            bool=false;
            for(int k=0;k<a.size();k++){
                if(arr[j][a.get(k)]==0)
                    break;
                bool=true;
            }
            if(bool)
                ans++;
        }
}
System.out.println(ans);

现在我知道我的解决方案是正确的，但它的时间复杂度是O(n^2)，我正在寻找一种更好的解决方案。谢谢！

- user11067275

1

@vivek -- 那样行不通；S2需要在第二个位置上有一个1的人。例如，一个值为4的人将无法组成一个可行的团队。 - Prune

1

@NicoSchertler：这个结论并不成立。有些问题可以计算出解的数量，而无需描述这些解。 - Prune

1

@vivek_23 是的！太好了。我把它直接降到了“O(n)”级别。非常感谢！ - user11067275

1

抱歉，我在写答案的时候读到了收到的评论。看起来 @vivek_23 和我采用了相同的方法。 - Prune

1

@user11067275 很高兴能帮忙 :) - nice_dev

显示剩余13条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Prune · Accepted Answer

您可以通过在存储科目组合时使用内存来减少学生数量的复杂性。

创建一个包含2^s个元素的列表，其中s是科目数量。将列表索引为科目组合，解释为二进制数。例如，S2的值为13，缺少2的值。

首先统计每个学生可以填补的“需求”。对于学生已知科目中的每个1位组合，在计数列表中递增该索引。

for student in student_list:

    score =   # student's covered subjects as an int

    tally = [0]*16
    for idx in range(16):
        if idx & score == idx:
            tally[idx] += 1

你现在有一个列表，其中列出了每种所需科目组合可覆盖多少学生。这是O(n * 2^s)

对于每个学生，找到所需分数，即该学生分数的补码。现在只需将所需分数的所有计数相加即可。

team_ct = 0

for student in student_list:

    needed =   # student's needed subjects as an int; this is 15-score (above)
    team_ct += tally[needed]

现在，每个配对都被计算了两次，因此将 team_ct 除以2。是的，这段最后的代码可以简化为一行：

team_ct = sum([tally[15-score] for score in foo]) / 2

当 foo 是所有学生成绩的结构时，这部分的时间复杂度是O(n)。