华为机试题：亮着电灯的盏数

我想了两种方法，第二种比第一种效率上有所提升：

import java.util.Scanner;

public class Main {

    private int n;//
    private boolean[] lights;

    /** * 输入 */
    public void input() {
        Scanner sc = new Scanner(System.in);
        try {
            n = sc.nextInt();
        } catch (Exception e) {
            n = 0;
        } finally {
            sc.close();
        }
    }
    /** * 解法一：循环次数n^2,时间复杂度是O(n^2) */
    public void turnOnOff() {
        if (n < 1 || n > 65535) {
            return;
        }
        long time1 = System.currentTimeMillis();
        lights = new boolean[n];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (j % i == 0) {
                    lights[j - 1] = lights[j - 1] ? false : true;
                }
            }
        }
        int count = 0;
        for (int j = 1; j <= n; j++) {
            if (lights[j - 1]) {
                count++;
            }
        }
        long time2 = System.currentTimeMillis();
        System.out.println(count + " 用时：" + (time2 - time1));
    }
    /** * 解法二：循环次数n(n+1)/2，虽然也是O(n^2)数量级，但是循环次数有所减少，效率得到提升 */
    public void turnOnOff2() {
        if (n < 1 || n > 65535) {
            return;
        }
        long time1 = System.currentTimeMillis();
        int onNum = 0;
        int[] lights = new int[n];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                if (i % j == 0) {
                    lights[i - 1]++;
                }
            }
            if ((lights[i - 1] & 1) == 1) {
                onNum++;
            }
        }
        long time2 = System.currentTimeMillis();
        System.out.println(onNum + " 用时：" + (time2 - time1));
    }

    public static void main(String[] args) {
        Main m = new Main();
        m.input();
        m.turnOnOff();
    }
}

• 解法一的思路：

以学生为中心，将学生遍历一遍，每一遍都要判断这个学生会开关哪些灯，学生遍历完以后，灯的最终状态就确定了。

• 解法二思路：

以灯为中心，将灯遍历一遍，每一遍都判断这个灯会被开关几次。只要学生的编号能整除灯的编号，这个学生就会开关灯一次，所以只要判断这个灯的序号能被哪些数整除（包括1和自身），就能知道这个灯会被开关几次，如果开关的次数是奇数，则最终是亮着的，如果开关次数为偶数，则最终是熄灭的。