public class 统计数字出现次数 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 3, 5, 3};
        // 核心思想是arr[i] == arr[j] 时，ar[arr[i]]和arr[arr[j]]映射到同一个位置
        work(arr, arr.length);
        int index = 1;
        for (int countResult : arr) {
            if (countResult < 0) {
                System.out.println(index++ + "出现了" + (-1) * countResult + "次");
            }
        }
    }

    public static void work(int[] arr, int n) {
        int index = 0;
        while (index < n) {
            // 因为数组都是从0开始的，所以arr[index]得减1才可以找到对应的元素，否则会数组越界
            int temp = arr[index] - 1;
            // 小于0说明当前位置是计数值，直接跳过
            if (temp < 0) {
                index++;
                continue;
            }
            if (arr[temp] > 0) {
                arr[index] = arr[temp];
                arr[temp] = -1;
            }
            // 找到自身
            else {
                arr[temp]--;
                arr[index] = 0;
            }
        }
    }
}

import java.util.Scanner;

/**
 * y^7 + 0.5y = x，给定x，求y
 *
 * 分析：f(y)单调，而且还是奇函数
 *
 * 那么只考虑x > 0的情况：
 *     由于f(y)单调，故考虑使用二分推出答案
 *     并且由原式可知，0.5 * y = x - y ^ 7 < x
 *       ---> 0 < y < 2 * x
 *
 */
public class 解指数方程 {

    private static double accuracy = 1e-8;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            double x = sc.nextDouble();
            double y = solve(x);
            System.out.printf("x = %f, y = %f\n", x, y);
        }
    }

    public static double solve(double x) {
        if (x == 0) {
            return 0;
        }
        boolean flag = x > 0;
        x = Math.abs(x);
        double left = 0, right = x;
        double mid = 0;
        while (left < right) {
            mid = (right - left) / 2 + left;
            double diff = calculate(mid) - x;
            if (Math.abs(diff) <= accuracy) {
                if (!flag) {
                    mid *= -1;
                }
                break;
            } else if (diff > 0) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return mid;
    }

    private static double calculate(double num) {
        return Math.pow(num, 7) + 0.5 * num;
    }
}

-100
x = -100.000000, y = -1.928028
1
x = 1.000000, y = 0.916197
0
x = 0.000000, y = 0.000000
100
x = 100.000000, y = 1.928028
38291
x = 38291.000000, y = 4.515693
37261.77321
x = 37261.773210, y = 4.498150
32918429
x = 32918429.000000, y = 11.855500

import java.util.Scanner;

public class 求算数平方根 {

    private static final double accuracy = 1e-8;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            double num = sc.nextDouble();

            // 二分
            long s1 = System.nanoTime();
            double mySqrt = sqrt(num);
            long e1 = System.nanoTime();

            // 牛顿迭代
            long s2 = System.nanoTime();
            double mySqrtByNewton = sqrtByNewton(num);
            long e2 = System.nanoTime();

            // jdk
            long s3 = System.nanoTime();
            double mathSqrt = Math.sqrt(num);
            long e3 = System.nanoTime();

            System.out.printf("二分法\t结果：%.8f\t耗时：%dns\n", mySqrt, e1 - s1);
            System.out.printf("牛顿迭代\t结果：%.8f\t耗时：%dns\n", mySqrtByNewton, e2 - s2);
            System.out.printf("JDK\t结果：%.8f\t耗时：%dns\n", mathSqrt, e3 - s3);

        }
    }


    /**
     * 二分
     */
    private static double sqrt(double num) {
        if (num < 0) {
            throw new RuntimeException(num + "负数无实平方根");
        }
        double left = 0, right = num;
        while (left < right) {
            double mid = (right - left) / 2 + left;
            if (Math.abs(mid - num / mid) < accuracy) {
                return mid;
            } else if (mid < num / mid) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return 0;
    }

    /**
     * 牛顿迭代
     * Xn+1 = (Xn + m / Xn) / 2;
     */
    private static double sqrtByNewton(double num) {
        double curr = num;
        double next = (curr + ( num / curr)) / 2;
        while (Math.abs(next - curr) > accuracy) {
            curr = next;
            next = (curr + ( num / curr)) / 2;
        }
        return next;
    }
}

41789241
二分法	结果：6464.45983822	耗时：34400ns
牛顿迭代	结果：6464.45983822	耗时：1600ns
JDK	结果：6464.45983822	耗时：800ns
421421421421
二分法	结果：649169.79398382	耗时：3800ns
牛顿迭代	结果：649169.79398382	耗时：1100ns
JDK	结果：649169.79398382	耗时：200ns
421421421422132
二分法	结果：20528551.37173912	耗时：4000ns
牛顿迭代	结果：20528551.37173912	耗时：1000ns
JDK	结果：20528551.37173912	耗时：200ns
1200000000
二分法	结果：34641.01615138	耗时：3000ns
牛顿迭代	结果：34641.01615138	耗时：900ns
JDK	结果：34641.01615138	耗时：200ns
100000000000000
二分法	结果：10000000.00000000	耗时：3700ns
牛顿迭代	结果：10000000.00000000	耗时：1100ns
JDK	结果：10000000.00000000	耗时：500ns