中级农民
- 积分
- 136
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2015-1-20
- 最后登录
- 1970-1-1
|
别小看这题。虽然算法原理不见得多复杂,但是其中会有很多的edge case。如果想把这些edge case用if else处理的话,代码的复杂度会大大增加的。
所以,你可以试着合并所有的edge case。
首先,你先把一个数组中的“每一个元素”和“每一个元素旁边的间隔”都看做一个“位置”。那么个N个元素的数组中,会有2N+1个这种位置。如果对于一个排好序的数组来说,你可以在第N个位置切一刀,这样切口两侧的元素肯定一样多,所以,中位数一定在切口的周围。如果这一刀正好切在“间隔”位置,那么切口左右两边的数的平均数即为中位数;如果这一刀正好切在“元素”位置,那么你可以理解为那个元素被切成了两半个,那么取这两半个的平均数,同样也是中位数。综合以上两种情况,一个矩阵的中位数肯定是(A[(N-1)/2] +A[N/2])/ 2,不需要判断数组个数。
这样的思路也可以推广到2个数组的情况。假设A数组有10个元素,即21个位置;B数组有7个元素,即15个位置。我现在一刀把这两个数组切开,那么如果希望中位数在这刀形成的两切口的周围,那么同样必须保证切口左右两边的”位置“数目一样多。例,如果这刀恰通过B数组的第7个位置,那么它也必须通过A数组的第10个位置 。如下图,双竖线表示切口的位置。
1 2 3 4 5 || 6 7 8 9 10
1 1 1 |1| 2 2 2
接下来,还必须进一步保证“两切口左侧的任一元素<=两切口右侧的任一元素”。如何判断这一点?只需保证:
A切口左侧的元素(A左)<=B切口右侧的元素(B右),
和B左< A右
即可。
以上图为例,A切口左右两侧的元素分别是5, 6. B切口左右两侧分别是1, 1 (因为它正好切到了一个元素上)。B左(1) <= A右(6),这点没有问题,但是A左(5) > B右(1),所以表示这种切法是不对的。
那么究竟怎么个不正确法?上面的推理说明A切口左侧依然有大于B中切口右侧的值,说明A中切口太偏右,B中切口太偏左。所以,我们把B中的切口调整到11(用二分法),同时A中的切口也要调整到17-11=6的位置。
此时有
1 2 3 || 4 5 6 7 8 9 10
1 1 1 1 2 |2| 2
B右(2)还是小于A左(3),还是不行,B切口继续向右到13,A切口在17-13=4处
1 2 || 3 4 5 6 7 8 9 10
1 1 1 1 2 2 |2|
此时终于满足切口左侧的元素都小于切口右侧的元素了。此时,中位数一定是两切口左侧两个元素的最大值(max(2,2)=2)和切口左侧两元素的最小值(min(3,2)=2)的平均数。也就是(2 + 2)/2 = 2.
用这种方法,你完全不需要判断数组元素是奇数还是偶数,代码量和普通的二分搜索基本没区别。唯一的特殊情况是,如果某个数组中的切口恰好到了数组的最左边的位置,那么此时”切口左边的数“就不存在了。这时人为地把切口左边的数当做INT_MIN即可。同理如果到了数组最右边,切口右边的数就是INT_MAX。只要两个数组不是都为空,那么切口左边的两个数不可能同时为INT_MIN,切口右边的数也不可能同时为INT_MAX,所以这两个数完全不会影响到最终结果。
我们永远在短的那个数组上做二分法,决定了短数组上切口位置,再确定长的数组的切口位置。为假设B的尺寸为M,A的尺寸为N。那么这个算法的算法复杂度是O(log(min(M, N))
我知道上面说的这些很难很难理解。但是,只要你能理解这个思路,代码会比大部分人的实现短得多。不妨一试。 |
|