鏁版嵁緇撴瀯絎簲绔犵畻娉曡璁￠[17]_璺ㄨ€冪綉

聽聽聽聽聽聽聽 1. 緇欏畾鏈?/span>m涓暣鏁扮殑閫掑鏈夊簭鏁扮粍a[1..m]鍜屾湁n涓暣鏁扮殑閫掑噺鏈夊簭鏁扮粍b[1..n]錛岃瘯鍐欏嚭綆楁硶:灝嗘暟緇?/span>a鍜?/span>b褰掑茍涓洪€掑鏈夊簭鏁扮粍c[l..m+n]銆?/span>(瑕佹眰錛氱畻娉曠殑鏃墮棿澶嶆潅搴︿負(fù)O(m+n))銆愬崕涓悊宸ュぇ瀛?/span> 2000 鍏€?/span>1錛?/span>10鍒嗭級(jí)銆?/span>

銆€銆€銆愬弬鑰冪瓟妗堛€?/span>

銆€銆€[棰樼洰鍒嗘瀽]鏁扮粍A鍜?/span>B鐨勫厓绱犲垎鍒湁搴忥紝嬈插皢涓ゆ暟緇勫悎騫跺埌C鏁扮粍錛屼嬌C浠嶆湁搴忥紝搴斿皢A鍜?/span>B鎷瘋礉鍒?/span>C錛屽彧瑕佹敞鎰?/span>A鍜?/span>B鏁扮粍鎸囬拡鐨勪嬌鐢紝浠ュ強(qiáng)姝ｇ‘澶勭悊涓€鏁扮粍璇誨畬鏁版嵁鍚庡皢鍙︿竴鏁扮粍浣欎笅鍏冪礌澶嶅埗鍒?/span>C涓嵆鍙€?/span>

銆€銆€void union(int A[],B[],C[],m,n)

銆€銆€//鏁村瀷鏁扮粍A鍜?/span>B鍚勬湁m鍜?/span>n涓厓绱狅紝鍓嶈€呴€掑鏈夊簭錛屽悗鑰呴€掑噺鏈夊簭錛屾湰綆楁硶灝?/span>A鍜?/span>B褰掑茍涓洪€掑鏈夊簭鐨勬暟緇?/span>C銆?/span>

銆€銆€{i=0; j=n-1; k=0;// i錛?/span>j錛?/span>k鍒嗗埆鏄暟緇?/span>A,B鍜?/span>C鐨勪笅鏍囷紝鍥犵敤C鎻忚堪錛屼笅鏍囦粠0寮€濮?/span>

銆€銆€while(i<m && j>=0)

銆€銆€if(a[i]<b[j]) c[k++]=a[i++] else c[k++]=b[j--];

銆€銆€while(i<m) c[k++]=a[i++];

銆€銆€while(j>=0) c[k++]=b[j--];

銆€銆€}綆楁硶緇撴潫