问题描述

思路分析

关键点：

1. 分数比较：

   • 对于每个学生，我们需要统计：
     • 分数小于或等于他的人数（lessOrEqual）。
     • 分数大于他的人数（greater）。
   • 如果 lessOrEqual > greater，他就会说谎。

2. 逐一遍历：

   • 对每个学生，统计班里符合上述条件的人数。
   • 简单的暴力解法是两层循环：外层遍历每个学生，内层统计所有学生分数与当前学生分数的关系。

解法步骤

1. 初始化：

   • 准备一个计数器 count，用来记录满足条件的学生数量。

2. 遍历每个学生：

   • 对于当前学生，统计分数小于或等于他的人数 lessOrEqual 和分数大于他的人数 greater。

3. 比较：

   • 如果 lessOrEqual > greater，增加计数器 count。

4. 输出结果：

   • 最后返回计数器 count。

参考代码（Java）

import java.util.Arrays;

public class Main {
    public static int solution(int[] A) {
        int n = A.length;
        int count = 0;

        for (int i = 0; i < n; i++) {
            // 分数 <= A[i] 的数量是 i+1 (因为数组是从0开始的索引)
            int lessOrEqual = 0;
            int greater = 0;

            for (int j = 0; j < n; j++) {
                if (A[j] <= A[i]) {
                    lessOrEqual++;
                } else {
                    greater++;
                }
            }

            // 如果分数 <= A[i] 的数量多于分数 > A[i] 的数量
            if (lessOrEqual > greater) {
                count++;
            }
        }

        return count;
    }

    public static void main(String[] args) {
        // 测试用例
        System.out.println(solution(new int[]{100, 100, 100}) == 3); // 所有学生都说谎
        System.out.println(solution(new int[]{2, 1, 3}) == 2); // 学生1和学生2说谎
        System.out.println(solution(new int[]{30, 1, 30, 30}) == 3); // 学生1、3、4说谎
        System.out.println(solution(new int[]{19, 27, 73, 55, 88}) == 3); // 学生1、2、3说谎
        System.out.println(solution(new int[]{19, 27, 73, 55, 88, 88, 2, 17, 22}) == 5); // 学生1、2、3、7、8说谎
    }
}

代码分析

1. 输入：

   • 接收一个整型数组 A，表示班级中每个学生的分数。

2. 变量：

   • n：数组长度，即学生总数。
   • count：记录满足条件的学生数量。

3. 双重循环：

   • 外层循环：逐个遍历每个学生，假设当前学生的分数是 A[i]。
   • 内层循环：统计所有其他学生与 A[i] 的分数关系：
     • lessOrEqual：分数小于或等于当前分数的人数。
     • greater：分数大于当前分数的人数。

4. 逻辑判断：

   • 如果 lessOrEqual > greater，说明当前学生符合条件，会说谎，计数器 count 增加。

5. 返回值：

   • 返回满足条件的学生数量 count。

复杂度分析

1. 时间复杂度：

   • 外层循环：遍历每个学生，总共 n 次。
   • 内层循环：对每个学生计算所有人的分数关系，总共也是 n 次。
   • 因此，时间复杂度为 $O(n^2)$。

2. 空间复杂度：

   • 使用了常量级别的额外变量（lessOrEqual 和 greater），因此空间复杂度为 $O(1)$。