分治法,o(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
* 【假币问题】 有n枚硬币,其中有一枚是假币,已知假币的重量较轻。现只有一个天平,要求用尽量少的比较次数找出这枚硬币。
*
* 【分析问题】 将n枚硬币分成相等的两部分: 1.当n为偶数时,将前后两部分,即 1...n/2
* 和n/2+1...0,放在天平的两端,较轻的一端里有假币,继续在较轻的这部分硬币中用同样的方法找出假币: 2.当n为奇数时,将前后两部分,即
* 1...(n-1)/2 和 (n+1)/2+1...0,放在天平的两端,较轻的一端里有假币,继续在较轻的这部分硬币中用同样的方法找出假币;
* 若两端重量相等,则中间的硬币,即第 (n+1)/2 枚硬币是假币。
*
* 【调用方式】 int cs[] = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2,}
* getCounterfeitCoint(cs, cs[0], cs[cs.length-1])
*
* @param coins
* @param first
* @param last
* @return
*/
static int getCounterfeitCoin(int coins[], int first, int last) {

int firstSum = 0, lastSum = 0, i;

if (first == last - 1) { // 只剩两枚
if (coins[first] < coins[last])
return first;

return last;
}

if ((last - first + 1) % 2 == 0) { // 偶数枚
for (i = first; i < (first + last) / 2; i++)
firstSum += coins[i];

for (i = first + (last - first) / 2 + 1; i < last + 1; i++)
lastSum += coins[i];

if (firstSum < lastSum)
return getCounterfeitCoin(coins, first, first + (last - first) / 2);
else
return getCounterfeitCoin(coins, first + (last - first) / 2 + 1, last);

} else { // 奇数枚

for (i = first; i < first + (last - first) / 2; i++)
firstSum += coins[i];

for (i = first + (last - first) / 2 + 1; i < last + 1; i++)
lastSum += coins[i];

if (firstSum < lastSum)
return getCounterfeitCoin(coins, first, first + (last - first) / 2 - 1);
else if (firstSum > lastSum)
return getCounterfeitCoin(coins, first + (last - first) / 2 - 1, last);
else
return (first + last) / 2;

}
}