【www.5929.com】命局的拍卖,多个n位的二进制整数相加难题PHP完成

四个n位二进制数分别存储在多个n元数组A和B中,那七个整数的和存在一个n+1元的数组C中
答:
此难点至关紧如果洞察相加进位的题材,元素1+1 =0 并且往前进一位
ADD-BINARY(A,B)
  C=new integer[A.length+1]
  carry=0
  for i=A.length downto 1
    C[i+1]=(A[i]+B[i]+carry)%2
    carry=(A[i]+B[i]+carry)/2
  C[i]=carry

1.大数储存

RSA 重视大数运算,方今主流RSA 算法都创设在512
到1024位的流年运算之上。而大多数的编译器只好协理到64位的平头运算,即大家在运算中所使用的平头必须低于等于64位,即:0xffff,
ffff,ffff.ffff,也就是18446744073709551615,那远远达不到RSA
的急需,于是须求尤其创造大数运算库来缓解这一难点。

最简便易行的法门是将命局当作数组举行处理,也就是将命局用0-9那十个数字组成的数组举办表
示,然后模拟人们手工举行“竖式总括”的进度编写其加减乘除函数。不过这么做效用很低,因为二进制为1024位的大数其十进制也有三百多位,对于任何一种
运算,都亟需在四个有数百个要素的数组空间上做多重循环,还亟需多多卓殊的空间存放统计的进退位标志及中间结果。其它,对于一些特殊的运算而言,选用二进
制会使计量进程大大简化,那种大数表示方法转化成二进制显著至极勤奋,所以在某些实例中则干脆采取了二进制数组的艺术来记录大数,那样效能就更低了。

一个一蹴而就的精雕细刻形式是将命局表示为一个n 进制数组,对于方今的32位系统而言n
可以取值为2
的32次方,即0x10000,0000,假若将一个二进制为1024位的气数转化成0x10000,0000进制,它就改为了32位,而每一位的取值范围就
不是二进制的0—1或十进制的0—9,而是0-0xffff,ffff,大家正好可以用一个无符号长整数来表示这一数值。所以1024位的大运就是一个有
32个要素的unsigned long数组,针对unsigned
long数组举行各样运算所需的轮回规模至多32次而已。而且0x10000,0000
进制与二进制,对于电脑来说,大约是四回事,转换万分简单。

譬如大数18446744073709551615,等于 ffffffff
ffffffff,就一定于十进制的99:有两位,每位都是ffffffff。而18446744073709551616
等于00000001 00000000 00000000,就一定于十进制的100:有三位,第四位是1
,其余两位是0,如此等等。在其实应用中,“数字”数组的排列顺序选取低位在前高位在后的方法,那样,大数A
就足以方便地用数学表明式来表示其值:A=Sum[i=0 to
n](A[i]*0x100000000 ^ i)(其中Sum
表示求和,A[i]代表用以记录A的数组的第i个要素,^表示乘方)。

其他整数运算最后都能分解成数字与数字之间的演算,在0x100000000
进制下其“数字”最大达到0xffffffff,其数字与数字之间的演算,结果也必将当先了方今32系统的字长。在VC++中,存在一个__int64
类型可以处理64位的平头,所以不要顾虑这一题材,而在任何编译系统中只要不设有64位整形,就要求使用更小的进制方式来囤积大数,例如WORD类型
(16位)可以用来代表0x10000 进制,但功能更高的格局如故使用32位的DWORD
类型,只然而将0x100000000
进制改成0x40000000进制,那样三个数字举办四则运算的最大结果为
0x3fffffff*
0x3fffffff,小于0xffffffff,只是不可以大致地用高位低位来将运算结果拆分成三个“数字”。

4.
Median of Two Sorted Arrays

UVALive 6911—Double Swords(贪心+树状数组(或集合)),uvalive

难题链接

www.5929.com, 

problem  description

Last night, Kingdom of Light was attacked by Kingdom of Dark! The queen
of Kingdom of Light, Queen Ar, was captured and locked inside a dark and
creepy castle. The king of Kingdom of Light, King Ash, wants to save the
queen. The castle is guarded by N dragons, conveniently numbered from 1
to N. To save Queen Ar, King Ash must kill all the dragons. The
kingdom’s oracle said that in order to kill the i-th dragon, King Ash
has to slay it with exactly two swords, one in each hand: one sword of
length Ai units, and another sword of length between Bi and Ci ,
inclusive. King Ash can carry unlimited number of swords, and each sword
can be used multiple times. The number of blacksmiths in the kingdom is
limited, so it is important to make as few swords as possible. Besides,
making swords is expensive and takes much time. Determine the minimum
number of swords the kingdom has to make so that King Ash can save Queen
Ar!

Input

The first line of input contains an integer T (T ≤ 20) denoting the
number of cases. Each case begins with an integer N (1 ≤ N ≤ 100, 000)
denoting the number of dragons which have to be killed. The next N lines
each contains three integers: Ai , Bi , and Ci (1 ≤ Ai ≤ 1, 000, 000; 1
≤ Bi ≤ Ci ≤ 1, 000, 000) denoting the swords’ length needed to kill the
i-th dragon as described in the above problem statement.

Output

For each case, output ‘Case #X: Y ’, where X is the case number starts
from 1 and Y is the minimum number of swords the kingdom has to make and
carry in order to defeat all the dragons and save Queen Ar.

Explanation for 1st sample case: The kingdom has to make two swords in
order to defeat one dragon.

Explanation for 2nd sample case: All the dragons can be defeated by
three swords, for example, with lengths of: 3, 6, and 15.

     • The fist dragon can be defeated by swords of length 3 and 6.

     • The second dragon can be defeated by swords of length 6 and 15.

【www.5929.com】命局的拍卖,多个n位的二进制整数相加难题PHP完成。     • The third dragon can be defeated by swords of length 3 and 15.

There also exists other combination of three swords.

Sample Input

4

1

7 6 8

3

3 5 10

6 11 15

3 13 15

4

1 10 20

3 50 60

2 30 40

4 70 80

2

5 100 200

150 1000 2000

Sample Output

Case #1: 2

Case #【www.5929.com】命局的拍卖,多个n位的二进制整数相加难题PHP完成。2: 3

Case #3: 8

Case #4: 3

 

题意:有n条恶龙,要求人同时持两把剑杀死,一把剑须要长为A,另一把剑长度在B~C之间,输入n条龙的A
B C数据要求,求最少须求辅导多少把剑?

思路:对于n组恶龙的数额,按照C的尺寸从左到右排序。先考虑数据A,即先把长度固定的剑需要的多寡确定,有些A相同只统计一遍,sum=0,sum+=unique(Ai)。然后考虑长度为距离(B~C)的剑,对于排好序的数额,循环处理,对于区间Bi~Ci
如若距离里从未剑或者有一把剑且长度和Ai相等,则添加一把剑长为Ci,sum++,那样可能在前边的距离中出现,使得剑的多寡最少,否则不处理,表明那几个间隔中有剑,不要求进入剑。注意:在认清距离中剑的数量时,用树状数组很有利查询;

 

代码如下:

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <bitset>
using namespace std;
const int maxn=1e6+5;
int c[maxn];
bool vis[maxn];
struct Node
{
    int x,y;
    int z;
}node[2*100005];
bool cmp(const Node s1,const Node s2)
{
    if(s1.y==s2.y) return s1.x<s2.x;
    return s1.y<s2.y;
}
int Lowbit(int t)
{
    return t&(t^(t-1));
}
void add(int x)
{
    while(x<maxn){
        c[x]++;
        x+=Lowbit(x);
    }
}
int sum(int x)
{
    int sum=0;
    while(x){
        sum+=c[x];
        x-=Lowbit(x);
    }
    return sum;
}
int main()
{
    int T,Case=1;
    cin>>T;
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        memset(c,0,sizeof(c));
        int N;
        scanf("%d",&N);
        for(int i=0;i<N;i++)
        {
            scanf("%d",&node[i].z);
            if(!vis[node[i].z]){
                add(node[i].z);
                vis[node[i].z]=true;
            }
            scanf("%d%d",&node[i].x,&node[i].y);
        }
        sort(node,node+N,cmp);
        for(int i=0;i<N;i++)
        {
            int t=sum(node[i].y)-sum(node[i].x-1);
            if(t==1&&node[i].z>=node[i].x&&node[i].z<=node[i].y)
                add(node[i].y);
            else if(!t) add(node[i].y);
        }
        printf("Case #%d: %d\n",Case++,sum(maxn-1));
    }
    return 0;
}

 

那题也足以用集合,其实和方面思路几乎,用集合判断距离中是或不是有剑;

在网上来看有人用set写,代码如下:

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <bitset>
using namespace std;
struct Node
{
    int x,y;
    int z;
}node[100005];
bool cmp(const Node s1,const Node s2)
{
    if(s1.y==s2.y) return s1.x<s2.x;
    return s1.y<s2.y;
}
set<int>s;
set<int>::iterator it;

int main()
{
    int T,Case=1;
    cin>>T;
    while(T--)
    {
        s.clear();
        int N;
        scanf("%d",&N);
        for(int i=0;i<N;i++)
        {
            scanf("%d",&node[i].z);
            s.insert(node[i].z);
            scanf("%d%d",&node[i].x,&node[i].y);
        }
        sort(node,node+N,cmp);
        int sum=0;
        for(int i=0;i<N;i++)
        {
            it=s.lower_bound(node[i].x);
            if(it!=s.end()&&*it==node[i].z) it++;
            if(it==s.end()||*it>node[i].y){
                if(node[i].z==node[i].y)
                    s.insert(0-node[i].y);
                   //sum++;///set有去重功能;
                else  s.insert(node[i].y);
            }
        }
        printf("Case #%d: %d\n",Case++,s.size()+sum);
    }
    return 0;
}

那样写确实AC了,但自身备感有BUG 我认真看了先后,想了一个数码:

1

2

4 2 4

4 4 6

毋庸置疑答案是2

运作那一个顺序结果是3

www.5929.com 1

 

而是用多重汇聚是可以防止那几个BUG的

代码如下:

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <bitset>
using namespace std;
const int maxn=1e6+5;
bool vis[maxn];
struct Node
{
    int x,y;
    int z;
}node[100005];
bool cmp(const Node s1,const Node s2)
{
    if(s1.y==s2.y) return s1.x<s2.x;
    return s1.y<s2.y;
}
multiset<int>s;
multiset<int>::iterator it;

int main()
{
    int T,Case=1;
    cin>>T;
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        s.clear();
        int N;
        scanf("%d",&N);
        for(int i=0;i<N;i++)
        {
            scanf("%d",&node[i].z);
            if(!vis[node[i].z]){
                s.insert(node[i].z);
                vis[node[i].z]=true;
            }
            scanf("%d%d",&node[i].x,&node[i].y);
        }
        sort(node,node+N,cmp);
        for(int i=0;i<N;i++)
        {
            it=s.lower_bound(node[i].x);
            if(it!=s.end()&&*it==node[i].z) it++;
            if(it==s.end()||*it>node[i].y){
                s.insert(node[i].y);
            }
        }
        printf("Case #%d: %d\n",Case++,s.size());
    }
    return 0;
}
/*
345
2
4 2 4
4 4 6
2
4 2 4
4 3 4
*/

 

6911—Double
Swords(贪心+树状数组(或集合)),uvalive 标题链接

<?php
function addBinary($A,$B){
        $C=array();
        $length=count($A);
        $carry=0;
        for($i=$length-1;$i>=0;$i--){
                //当前位的数字逻辑 1+1=0 1+0=1
                $C[$i+1]=($A[$i]+$B[$i]+$carry)%2;
                //进位的数字逻辑  1+1=1 1+0=0
                $carry=intval(($A[$i]+$B[$i]+$carry)/2);
        }   
        $C[$i+1]=$carry;
        return $C; 
}

$A=array(0,1,1,0);
$B=array(1,1,1,1);
$C=addBinary($A,$B);
var_dump($C);

2.加法

设:

A=Sum[i=0 to p](A[i]*0x100000000^i)

B=Sum[i=0 to q](B[i]*0x100000000^i),p>=q

C=Sum[i=0 to n](C[i]*0x100000000^i)=A+B

显然:

C[i]不是粗略地等于A[i]+B[i],因为假诺C[i]>0xffffffff就需要进位,当然统计

C[i-1]时也说不定发生了进位,所以总计C[i]时还要加上上次的进位值。

如果用carry[i]笔录每回的进位则有:

C[i]=A[i]+B[i]+carry[i-1]-carry[i]*0x100000000

其中carry[-1]=0

若A[i]+B[i]+carry[i-1]>0xffffffff,则carry[i]=1;反之则carry[i]=0

若carry[p]=0,则n=p;反之则n=p+1

There are two sorted arrays nums1 and nums2 of size m and n respectively.

 

3.减法

设:

A=Sum[i=0 to p](A[i]*0x100000000^i)

B=Sum[i=0 to q](B[i]*0x100000000^i),p>=q

C=Sum[i=0 to n](C[i]*0x100000000^i)=A-B

显然:

C[i]不是简约地等于A[i]-B[i],因为只要A[i]

C[i-1]时也说不定暴发了借位,所以总计C[i]时还要减去上次的借位值。

如果用carry[i]记录每一次的借位则有:

C[i]=A[i]+carry[i]*0x100000000-B[i]-carry[i-1]

其中carry[-1]=0

若A[i]>B[i]则carry[i]=0;反之则carry[i]=1

若C[p]=0,则n=p-1;反之则n=p

Find the median of the two sorted arrays. The overall run time
complexity should be O(log (m+n)).

4.乘法

设:

A=Sum[i=0 to p](A[i]*0x100000000^i)

B=Sum[i=0 to q](B[i]*0x100000000^i),p>=q

C=Sum[i=0 to n](C[i]*0x100000000^i)=A*B

显然:

C=Sum[i=0 to q](A*B[i]*0x100000000^i)

而(A*B[i]*100000000^i)=Sum[j=0 to
p](A[j]*B[i]*0x100000000^(i+j))

所以C=Sum[i=0 to q](Sum[j=0 to
p](A[j]*B[i]*0x100000000^(i+j)))

因此:

C[i]=Sum[j=0 to
q](A[i-j]*B[j])+carry[i-1]-carry[i]*0x100000000

其中carry[-1]=0

carry[i]=(Sum[j=0 to q](A[i-j]*B[j])+carry[i-1])/0x100000000

n=p+q-1,若carry[n]>0,则n=n+1,C[n]=carry

Example 1:

5.除法

设:

A=Sum[i=0 to p](A[i]*0x100000000^i)

B=Sum[i=0 to q](B[i]*0x100000000^i),p>=q

C=Sum[i=0 to n](C[i]*0x100000000^i)=A/B

出于无法将B 对A
“试商”,大家不得不转换成B[q]对A[p]的试商来得到一个接近值,

于是大家不可能间接总括C。可是,我们得以一步一步地逼近C

显然:

(A[p]/B[q]-1)*0x100000000^(p-q)

令:

X=0

重复:

A=A-X*B,X=X+(A[p]/B[q]-1)*0x100000000^(p-q),直到A

则有:

X=C

注意:

由于大数可了解为0x100000000进制,所以对于自由大数A*0x100000000^k

都等价于将A 的数组中的各要素左移k 位,不必计算;同样,除法则相当于右移

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

6.取模

设:

A=Sum[i=0 to p](A[i]*0x100000000^i)

B=Sum[i=0 to q](B[i]*0x100000000^i),p>=q

C=Sum[i=0 to n](C[i]*0x100000000^i)=A%B

求模与求商的历程一样,只是出于不须求记录商而尤为简约:

重复:

A=A-(A[p]/B[q]-1)*0x100000000^(p-q)*B,直到A

则有:

A=C

Example 2:

7.二元四遍方程

在RSA 算法中,往往要在已知A、M的场馆下,求 B,使得
(A*B)%M=1。即一定于求解B、N都是未知数的二元一遍不定方程
A*B-M*N=1,的细小整数解。

而针对不定方程ax-by=1
的蝇头整数解,古今中外都举行过详细的钻研,西方有闻名的欧几里德算法,即辗转相除法,中国有秦九韶的“大衍求一术”。欧几Reade算法是一种递归算法,相比较简单领会:

例如:11x-49y=1,求x

(a) 11 x – 49 y = 1    49%11=5 ->

(b) 11 x –  5 y = 1    11%5 =1 ->

(c)    x –  5 y = 1

令y=0 代入(c)得x=1

令x=1 代入(b)得y=2

令y=2 代入(a)得x=9

同理可使用递归算法求得任意
ax-by=1(a、b互质)的解,实际上通过分析归咎将递归算法转换成非递归算法就变成了大衍求一术。

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

8.幂模运算

幂模运算是RSA 主旨算法,最直白地决定了RSA
算法的质量,针对高速幂模运算这一课题,许多天堂现代数学家指出了大气的化解方案。平时都是先将幂模运算化简为乘模运算。

例如求D=C^15 % N,由于:

a*b % n = (a % n)*(b % n) % n

所以:

C1=C*C % N       =C^2 % N

C2=C1*C % N      =C^3 % N

C3=C2*C2 % N     =C^6 % N

C4=C3*C % N      =C^7 % N

C5=C4*C4 % N     =C^14 % N

C6=C5*C % N      =C^15 % N

即:

对此E=15的幂模运算可解释为6个乘模运算

汇总分析以上办法可以窥见对于任意E,可应用以下算法统计D=C^E % N:

D=1

WHILE E>=0

IF E为奇数

D=D*C % N

D=D*D % N

E=E-1

IF E为偶数

D=D*D % N

E=E/2

RETURN D

再加以分析会发觉,要通晓D 几时需乘 C,不要求频仍对E
进行减一或除二的操作,只必要验证E 的二进制个位是0 照旧1
就足以了,而且从左至右验证和从右至左验证都行,反而从左至右验证更简便:

若E=Sum[i=0 to n](E[i]*2^i),0<=E[i]<=1(E为二进制)

D=1

FOR i=n TO 0

D=D*D % N

IF E[i]=1

D=D*C % N

RETURN D

题意精通:

9.乘模运算

结余的题目就是乘模运算了,对于A*B % N,要是A、B
都是1024位的运气,先计算A*B,再%
N,就会生出2048位的中档结果,假设不利用动态内存分配技术就必须将命运定义中的数组空间增加一倍,那样会促成大批量的荒废,因为在大部情形下不会
用到那额外的一倍空间,而利用动态内存分配技术会使大数存储失去延续性而使运算进程中的循环操作变得突出繁琐。所以计算的重中之重条件就是要避免统计A*B。

由于:

A*B=A*(Sum[i=0 to n](B[i]*0x100000000^i))

所以:

A*B % N = (Sum[i=0 to n]((A*B[i])*0x100000000^i)) % N

可以用一个循环求得:

C=0;

FOR i=0 to n

C=C+A*B[i]*0x100000000 % N

RETURN C

其实,有一种蒙哥马利算法可以更快地形成数次巡回的乘模运算,然则其原理涉及较多的数论知识,且达成起来比较费心,对进程虽有进步,经测试也不会超越一个数量级,所以暂且不予考虑。

加以任意四个曾经排好序的数组,
要你求那五个数组的中位数. 并且时间复杂度无法当先O(log (m+n) )

10.素数测试

数论学家利用费马小定理( a^(p-1)%p=1,其中p是质数,a是整数
)研讨出了多种素数测试方法,方今最快的算法是拉宾Miller测试算法,测试N是素数的长河如下:

(1)计算奇数M,使得N=(2^r)*M+1

(2)拔取随机数A

(3)对于任意i

(4)或者,若A^M MOD N = 1,则N通过任意数A的测试

(5)让A取不相同的值对N进行5次测试,若一切通过则判定N为素数

若N 通过一回测试,则N 不是素数的几率为 25%,若N 通过t 次测试,则N
不是素数的票房价值为1/4^t。事实上取t 为5 时,N 不是素数的几率为 1/128,N
为素数的几率已经高于99.99%。

在其实使用中,可率先用300—500个小素数对N
进行测试,以坚实拉宾Miller测试通过的票房价值,从而升高测试速度。而在扭转随机素数时,选拔的随机数最好让
r=0,则可省去手续(3) 的测试,进一步升高测试速度。

思路历程:

11.输入输出

天命的输入输出是通过字符串来形成的,事实上很不难已毕,例如依据十进制格式举行拍卖,则:

输入:

X=0

FOR i=0 TO n

X=X*10

X=X+(int)(str[n]-48)

RETURN X

输出:

str=

WHILE(X>0)

str=(char)(X%10-48)+str

RETURN str

  1. 统一成一个数组,
    再求其中位数. 于是想到了联合的算法(按思考的岁月先后)

  2. 插入排序. 粗略一算,
    时间复杂度为O(m*n).

  3. 二分插入. 粗略一算, 复杂度为 O(nlogm),
    (倘诺n<m)

可以看出要高达log(m+n)这一个阶段,
合并那条路走不通.

  1. 逆推法.
    假若成功集合了nums1(简称A,长度为n) 和nums2(简称B,长度为m), 得到一个数组C
    .通过观望C和它的中位数median可开头取得以下结论

  2. C.length = m + n

  3. 对此自由的 c1 ∈ C1, c2 ∈ C2 均有 c1
    <= c2, 即 MAX(C1) <= MIN(C2)
  4. median可把M分成左半有的(C1),
    和右半部分(C2).  并且C1.length == C2.length (或 C1.length ==
    C2.length + 1, 将median放在C1)

中位数为 median = (MAX(C1) + MIN(C2)) /2
 (m+n 为偶数) 或 MAX(C1)  (m+n为奇数). (将median放在C1)

则义务转换为, 已知 A,B ,
求满意上述标准的 MAX(C1),MIN(C2)
 

要满足条件1: 很不难满意….

要满意条件2:  由MAX(C1) <= MIN(C2)
可知

  1. MAX(C1中 来自A的要素) <= MIN(C2中
    来自A的要素) (分明创设)

  2. MAX(C1中 来自A的元素) <= MIN(C2中
    来自B的元素)

  3. MAX(C1中 来自B的元素) <= MIN(C2中
    来自B的因素) (鲜明成立)

  4. MAX(C1中 来自B的元素) <= MIN(C2中
    来自A的元素) 

要满足条件3: C1.length ==
C2.length
 (或 C1.length  == 1+ C2.length , 将median放在C2) , 设C1中
来自A的个数为x, 来自B的个数为y, 要知足

  1. C1.length = x + y , C2.length = m +
    n – x – y  (或 m + n – x – y + 1)

即满意  y = (m + n + 1) /2  – x
 (利用除2向下取整,合并三种意况)

what?那么些姿势的趣味就是 C1中
A的个数和B的个数满意线性关系, 那表示什么? 

那意味着 只要找到 x (C1中 A元素的数额) ,
使得A,B 满意 条件2即可. 此话怎讲?

一个(x,y)的撤并如图:

www.5929.com 2www.5929.com 3

即满足:

  • A[x-1] <= B[y]
  • B[y-1] <= A[x]

临界值有 x =0, x = n , y = 0 , y =
m(稍后商量)

  • 将x 从 0 到 n 进行依次遍历,
    那样复杂度为O(n)
  • 从0到n 对x 举行二分查找,
    那样复杂度为O(logn)

看来,
难题是可化解并且符合标题必要的.

取得初阶获得算法:

var left = 0;
    var right = A.length;
    while(left <= right)
    {
        var x = (left + right) / 2;
        var y = (A.length + B.length + 1) / 2 - x;
        if(A[x-1] > B[y])
        {
            //说明A[x-1]太大了.
            //如果 x增大, 则y会减少, 这样A[x-1]会更加比B[y]大.
            //所以 x应该减少.
            right = x;
        }
        else if(B[y-1] > A[x])
        {
            //说明A[x]太小了
            //如果 x减小,则 y会增大, 这样B[y-1]会比A[x]更大.
            //所以 x应该增大.
            left = x;
        }
        else {
            //说明x刚好满足条件2.
            var MAXA = A[x-1];
            var MINB = B[y];
            if((A.length + B.length )%2 == 0)
            {
                return (MAXA + MINB) / 2;
            }
            else{
                return MAXA*1.0;
            }
        }
    }

上面探究 x=0 , x=n, y=0, y=m的情况

那多种景况, 对应的是

  • C1中 A为空集 (导致A[x-1] 不存在)
  • C2中 A为空集 (导致A[x]不存在)
  • C1中 B为空集 (导致B[y-1]不存在)
  • C2中 B为空集 (导致B[y]不存在)

若出现这两种, 将其视为满足条件

则有:

if (x !== 0 && y !== B.length && A[x - 1] > B[y]) {
    //说明A[x-1]太大了.
    //如果 x增大, 则y会减少, 这样A[x-1]会更加比B[y]大.
    //所以 x应该减少.
    right = x - 1;
}
else if (y !== 0 && x !== A.length && B[y - 1] > A[x]) {
    //说明A[x]太小了
    //如果 x减小,则 y会增大, 这样B[y-1]会比A[x]更大.
    //所以 x应该增大.
    left = x + 1;
}

在获取最后结果的时候要也要认清:

//说明x刚好满足条件2.
            if (x === 0) {
                var MAX_C1 = B[y - 1];
            }
            else if (y === 0) {
                var MAX_C1 = A[x - 1];
            }
            else {
                var MAX_C1 = A[x - 1] > B[y - 1] ? A[x - 1] : B[y - 1];
            }

            if (x === A.length) {
                var MIN_C2 = B[y];
            }
            else if (y === B.length) {
                var MIN_C2 = A[x];
            }
            else {
                var MIN_C2 = A[x] > B[y] ? B[y] : A[x];
            }

            if ((A.length + B.length) % 2 == 0) {
                return (MAX_C1 + MIN_C2) / 2;
            }
            else {
                return MAX_C1 * 1.0;
            }

以下为完整代码:

/**
 * @param {number[]} A
 * @param {number[]} B
 * @return {number}
 */
var findMedianSortedArrays = function (A, B) {
    //确保 A.length < B.length 实现 log(MIN(m,n))
    if (A.length > B.length) {
        var temp = B;
        B = A;
        A = temp;
    }
    var left = 0;
    var right = A.length;
    while (left <= right) {
        var x = parseInt((left + right) / 2);
        var y = parseInt((A.length + B.length + 1) / 2) - x;
        if (x !== 0 && y !== B.length && A[x - 1] > B[y]) {
            //说明A[x-1]太大了.
            //如果 x增大, 则y会减少, 这样A[x-1]会更加比B[y]大.
            //所以 x应该减少.
            right = x - 1;
        }
        else if (y !== 0 && x !== A.length && B[y - 1] > A[x]) {
            //说明A[x]太小了
            //如果 x减小,则 y会增大, 这样B[y-1]会比A[x]更大.
            //所以 x应该增大.
            left = x + 1;
        }
        else {
            //说明x刚好满足条件2.
            if (x === 0) {
                var MAX_C1 = B[y - 1];
            }
            else if (y === 0) {
                var MAX_C1 = A[x - 1];
            }
            else {
                var MAX_C1 = A[x - 1] > B[y - 1] ? A[x - 1] : B[y - 1];
            }

            if (x === A.length) {
                var MIN_C2 = B[y];
            }
            else if (y === B.length) {
                var MIN_C2 = A[x];
            }
            else {
                var MIN_C2 = A[x] > B[y] ? B[y] : A[x];
            }

            if ((A.length + B.length) % 2 == 0) {
                return (MAX_C1 + MIN_C2) / 2;
            }
            else {
                return MAX_C1 * 1.0;
            }
        }
    }
};

Leave a Comment.