减治法求解假币问题

对任意N枚硬币 存在一枚假币且不知知道过轻还是过重 巧妙使用减治法求解

○算法思想——减治法

具体思路如下：

通过三种策略进行减治即可计算任意N枚硬币中未知的一枚假币 （完全原创！）

1. 当硬币数量为3的倍数时

   对硬币分为三组进行称重

   若出现三组有一组不同

   则找出不同的一组并记录是轻还是重 递归分析不同的一组

   若三组都相同则返回 -1 表示找不到

2. 当硬币的数量为2的倍数且已知假币轻重

   将硬币分为两组称重

   若两组等重则返回 -1 表示找不到

   若假币较重 则递归分析较重一组

   若假币较轻 则递归分析较轻一组

3. 若不满足 1、2

   计算当前硬币数量与3的余数（1 or 2）

   递归分析去除余数数量的硬币

   若结果不为 -1 则直接返回结果

   若余数为 1 则假币为最后一个

   若余数为 2 则递归分析最后三个硬币即得出结果

○时间复杂度

最高
$$
O(\log_2N)
$$
最低
$$
O(\log_3N)
$$

○实现代码

public class FakeCoin {
    public static int fakeWeight = 0;

    public static int getWeight(int[] coins, int start, int end) {
        int total = 0;
        for (int i = start; i <= end; i++) {
            total += coins[i];
        }
        return total;
    }

    public static int find3part(int[] coins, int start, int end, int size) {
        int part1 = start + size / 3;
        int part2 = start + size * 2 / 3;
        int p1w = getWeight(coins, start, part1 - 1);
        int p2w = getWeight(coins, part1, part2 - 1);
        int p3w = getWeight(coins, part2, end);
        if (p1w == p2w && p2w == p3w) {
            return -1;
        }
        if (p1w == p2w) {
            fakeWeight = p3w - p2w;
            return find(coins, part2, end);
        } else if (p1w == p3w) {
            fakeWeight = p2w - p1w;
            return find(coins, part1, part2 - 1);
        } else {
            // (p2w == p3w)
            fakeWeight = p1w - p2w;
            return find(coins, start, part1 - 1);
        }
    }

    public static int find(int[] coins, int start, int end) {
        int size = end - start + 1;
        if (size == 1) {
            return start;
        }
        if (size % 3 == 0) {
            return find3part(coins, start, end, size);
        } else if (size % 2 == 0 && fakeWeight != 0) {
            return find2part(coins,start,end,size);
        } else {
            int left = size % 3;
            int res = find(coins, start, end - left);
            if (res != -1) {
                return res;
            }
            if (left == 1) {
                return end;
            } else {
                // left == 2
                return find3part(coins, end - left, end, 3);
            }
        }
    }

    private static int find2part(int[] coins, int start, int end, int size) {
        int mid = start + size / 2;
        int p1w = getWeight(coins, start, mid - 1);
        int p2w = getWeight(coins, mid, end);
        if (p1w == p2w) return -1;
        //假币较重
        if (fakeWeight > 0) {
            return p1w < p2w ? find(coins,mid, end)
                    : find(coins, start, mid-1);
        } else { //假币较轻
            return p1w > p2w ? find(coins,mid, end)
                    : find(coins, start, mid-1);
        }
    }

    public static int run(int[] coins) {
        if (coins.length < 3) {
            return -1;
        }
        return find(coins, 0, coins.length - 1);
    }

    public static void main(String[] args) {
        int[] coins = new int[RandomUtil.randomInt(888,9999)];
        Arrays.fill(coins, 1);
        int trueRes = RandomUtil.randomInt(0, coins.length - 1);
        coins[trueRes] = 0;
        System.out.println("total " + coins.length + " coins, true result is " + trueRes);
        System.out.println(TimeCalc.call(FakeCoin::run, coins).toString());
    }

}