ยาก 1 ข้อที่แก้แล้ว อัตราผ่าน 100.0%

Median of Two Sorted Arrays

Find the median of two sorted lists combined.

สิ่งที่คุณจะได้เรียนรู้

  • Partition two sorted arrays with binary search
  • Find the median in O(log n)
  • Handle even and odd total lengths

โจทย์

ดูฉบับแปล

Both lists are sorted in ascending order. Find the median of all their numbers together; for an even count it is the average of the two middle values. An O(log(m + n)) partition search is possible, but any correct method within the limits is accepted.

Implement median_of_two(first, second).

Input

first: A sorted list. second: A sorted list.

Output

Return the median.

เงื่อนไข

0 ≤ lengths ≤ 100,000; the combined length is at least 1

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
first = [1, 3]
second = [2]

ผลลัพธ์ที่คาดหวัง:
expected = 2.0
อินพุต:
std::vector<long long> first = {1, 3};
std::vector<long long> second = {2};

ผลลัพธ์ที่คาดหวัง:
double expected = 2.0;
อินพุต:
long[] first = new long[] {1, 3};
long[] second = new long[] {2};

ผลลัพธ์ที่คาดหวัง:
double expected = 2.0;

คำอธิบาย

Combined: [1, 2, 3]; the middle value is 2.

ตัวอย่างที่ 2
อินพุต:
first = [1, 2]
second = [3, 4]

ผลลัพธ์ที่คาดหวัง:
expected = 2.5
อินพุต:
std::vector<long long> first = {1, 2};
std::vector<long long> second = {3, 4};

ผลลัพธ์ที่คาดหวัง:
double expected = 2.5;
อินพุต:
long[] first = new long[] {1, 2};
long[] second = new long[] {3, 4};

ผลลัพธ์ที่คาดหวัง:
double expected = 2.5;

คำอธิบาย

Combined: [1, 2, 3, 4]; (2 + 3) / 2 = 2.5.

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

The combined order matters, but you do not need to merge everything if you can find the middle split directly.

คำใบ้ 2

Search for a partition where left halves contain exactly the lower middle elements and every left value is no larger than every right value.

คำใบ้ 3

Handle empty arrays and both odd and even total lengths carefully, since the median may come from one middle value or two.

ความซับซ้อนที่คาดหวัง

O(log(min(m, n))) time, O(1) extra space

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

# นักโค้ด ภาษา เวลา หน่วยความจำ คะแนนจาก AI คำตอบ
1 ННикита Python 825 ms - 5/5 ดูโค้ด

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

สปอยล์: มีคำตอบเต็ม 1 ข้อด้านล่าง ลองแก้ด้วยตัวเองก่อน คุณยังสามารถดูโค้ดของนักพัฒนาคนอื่นและรีวิว AI ได้ เข้าสู่ระบบและแก้โจทย์เพื่อร่วมพูดคุย