找兩個有序陣列的中位數的幾種方式

2021-05-05 10:42:22 字數 3882 閱讀 8459

1樓:影月

我用5個思路的來解決兩個非減序陣列的中位數.但是成功的只有四個,思路3邊界問題太嚴重.

有時間再來弄好他,他在考試中也不適合使用(邊界問題沒法快速解決,網上也有人說小資料列舉法確定邊界),總的來說費事.

主函式:

思路一:

/*方法1:採用歸併兩個非減陣列形成新非減陣列,然後求取新陣列的中位數.

效能分析:歸併兩陣列的時間複雜度o(n+m),查詢中位數時間複雜度o(1).所以時間複雜度o((n+m)*1)=o(m+n)

*/double findmediansortedarrays_1(int* nums1, int nums1size, int* nums2, int nums2size) ;

double mid_f = (nums1size + nums2size);

int sign = (!((int)mid_f & 0x1));

if ((!nums1size) && (!nums2size))return -1;

/* mid_f = (mid_f / 2);

if (nums1size == 0)

if (nums2size == 0)  */

while ((i < nums1size) && (j < nums2size))

while (i < nums1size)

while (j < nums2size)

// mid_f = (k & 0x1)? (c[(k / 2)]):(((c[(k / 2 + sign)]) + (c[(k / 2)])) / 2);

mid_f = (((c[(k / 2 - sign)]) + (c[(k / 2)])) / 2);

printf("ok k = %d  (nums1size + nums2size) = %d  i = %d j  = %d  \r\n", k, (nums1size + nums2size), i, j);

i = 0;

while(i <= k)

return mid_f;

}思路二:

double findmediansortedarrays_2(int* nums1, int nums1size, int* nums2, int nums2size)

else

}double sss(int a, int m, int b, int n, int k)

方法三:

double findmediansortedarrays_3(int* nums1, int nums1size, int* nums2, int nums2size)

else if (nums1size == 1)

else

else}}

//這裡要考慮nums2[(mid2 - k)]和nums2[(mid2 + k)] (k=1,2,...length(nums2)/2)同nums2[mid2]是否相等的情況!!這樣才能保證邊界清晰.

else

else if (nums1[0] >= nums2[(mid2 + 1)])

else /*nums2[(mid2 - k)] nums1[mid1 + 1])

else}}

//這裡要考慮nums1[(mid1 - k)]和nums1[(mid1 + k)] (k=1,2,...length(nums1)/2)同nums1[mid1]是否相等的情況!!這樣才能保證邊界清晰.

else

else if (nums2[0] >= nums1[(mid1 + 1)])

else /*nums1[(mid1 - k)]

方法四:

/* 從某種程度上來說這是每陣列的中位數對比法的一種更完善的思想.通過對比每陣列的割處,a[li] nums2size)

while (low <= high)

else if (lb > ra)

else

}return ((((la >= lb) ? (la) : (lb)) + ((ra <= rb) ? (ra) : (rb))) / 2);

}leetcode-;兩有序陣列找中位數答案

方法五:

/* 用統計方法,從小到大對兩陣列同時進行歸併式的遍歷,並計數.當計數值等於兩陣列的中位數的下標,就找到中位數.

效能分析:時間複雜度是歸併時間複雜度的一半,即o(m+n)=o((m+n)/2)

*/double findmediansortedarrays_5(int* nums1, int nums1size, int* nums2, int nums2size)

if (nums2size == 0)

if (sign)

middle = (nums1[j] <= nums2[k]) ? (nums1[j--]) : (nums2[k--]);//偶數中位數的前半部分最大值

middle = ((middle + ((nums1[j] <= nums2[k]) ? (nums1[j]) : (nums2[k]))) / 2);//[偶數中位數的後半部分最小值 + middle(偶數中位數的前半部分最大值)] / 2 = middle

}else

middle = (nums1[j] <= nums2[k]) ? (nums1[j]) : (nums2[k]);

}return middle;

}測試結果:(出現的特例:這著實具有不可避免性.輸入全體樣本中重複率高時,結束條件能被錯誤觸發.)

/*ok k = 24  (nums1size + nums2size) = 24  i = 11 j  = 13

c[0] = 0

c[1] = 2

c[2] = 4

c[3] = 5

c[4] = 5

c[5] = 6

c[6] = 7

c[7] = 9

c[8] = 9

c[9] = 10

c[10] = 15

c[11] = 15

c[12] = 17

c[13] = 18

c[14] = 20

c[15] = 21

c[16] = 23

c[17] = 23

c[18] = 24

c[19] = 25

c[20] = 26

c[21] = 27

c[22] = 29

c[23] = 50

c[24] = 0

中位數 16.000000

中位數 16.000000

nums1size = 11   nums1[5] = 9     nums2size = 13  nums2[6] = 20

nums1size = 6   nums1[3] = 21     nums2size = 7  nums2[3] = 15

nums1size = 4   nums1[2] = 15     nums2size = 4  nums2[2] = 18

nums1size = 2   nums1[0] = 15     nums2size = 3  nums2[1] = 17

nums1size = 2   nums1[0] = 15     nums2size = 2  nums2[0] = 15

中位數 15.000000

la = 9  ra = 9          lb = 20 rb = 20

la = 21 ra = 21         lb = 15 rb = 15

la = 10 ra = 15         lb = 17 rb = 18

la = 15 ra = 15         lb = 17 rb = 17

la = 15 ra = 21         lb = 15 rb = 17

中位數 16.000000

中位數 16.000000*/

怎樣比較兩個角的大小,怎樣來比較兩個兩位數的大小

比較兩個角的大小可以用疊合法。就是把兩角的頂點和一邊疊合在一起,另一邊落在第一條邊的同旁。如果這另一邊重合,那麼這兩個角相等。如果這另一邊不重合,必然發現一個角的這條邊在另一個角的內部,那麼前面所說的角小 如果這條邊在另一個角的外部,那麼前面所說的角大。但要注意角的大小隻與開口大小有關,而與角的邊畫...

吱的兩個讀音,「吱吱」有幾種讀音?

一 吱的讀音 z zh 二 部首 口 三 釋義 1 象聲詞,形容某些聲音。2 聲 方言,做聲,如 我反覆問了幾次,他就是不 四 筆畫 豎 橫折 橫 橫 豎 橫撇 橫鉤 捺。擴充套件資料 1 吱嘍 z lou 見 吱嘍嘍 2 吱嗻 z zh 象聲詞。形容人的嘈雜聲。3 格吱 g z 用手撓人胳肢窩使人...

兩個兩位數相加的和是99,且加數的十位數相同,這兩個兩位數可能是多少

設一個數個位是x,十位是y 則 x 10y 10x y 99 得11x 11y 99 x y 9所以當 x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 y 8 y 7 y 6 y 5 y 4 y 3 y 2 y 1因此,這兩個兩位數是 18,81 27,72 36,63 45,54 ...