Trung vị của 2 mảng sắp xếp

0 0 0

Người đăng: Minh Penguin

Theo Viblo Asia

Đề bài

Cho 2 mảng đã được sắp xếp tăng dần , tìm trung vị (median) của 2 mảng này

Hướng tiếp cận

  1. Chia làm 2 mảng 1 và 2 và thực hiện binary search trên mảng nhỏ hơn

  2. Dựa trên công thức l1≤r2andl2≤r1 bảo đảm các phần tử nằm bên trái mảng được chọn sẽ nhỏ hơn bên phải. Trong đó:

  • l1: Phần tử lớn nhất bên trái mảng 1.
  • r1: Phần tử nhỏ nhất bên phải mảng 1.
  • l2: Phần tử lớn nhất bên trái mảng 2.
  • r2: Phần tử nhỏ nhất bên phải mảng 2. Kết quả:
  1. Tính kết quả:
  • Nếu tổng số phần tử là lẻ, median là phần tử lớn nhất ở nửa bên trái: max(l1,l2).
  • Nếu tổng số phần tử là chẵn, median là trung bình cộng của hai phần tử nằm ở "giữa": max(l1,l2)+min(r1,r2) / 2

Code

class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: len1 = len(nums1) # len of arr1 len2 = len(nums2) # len of arr2 if len1 > len2: return self.findMedianSortedArrays(nums2, nums1) total_len = len1 + len2 mid = (len1 + len2 + 1) // 2 low = 0 high = len1 while low <= high: mid1 = (low + high) // 2 # mid index of arr 1 mid2 = mid - mid1 # mid index of arr 2 l1 = float('-inf') l2 = float('-inf') r1 = float('inf') r2 = float('inf') if mid1 < len1: r1 = nums1[mid1] if mid2 < len2: r2 = nums2[mid2] if mid1 - 1 > -1: l1 = nums1[mid1-1] if mid2 - 1 > -1: l2 = nums2[mid2-1] if l1<=r2 and l2<=r1: if total_len % 2 == 1: return max(l1, l2) return (max(l1,l2) + min(r1,r2)) / 2 elif l1 > r2: high=mid1-1 else: low = mid1 + 1 return 0.0

Bình luận

Bài viết tương tự

- vừa được xem lúc

Thuật toán Binary Search, tìm kiếm nhị phân! Implement code

Xin chào bét fờ zen. .

0 0 35

- vừa được xem lúc

Tìm kiếm nhị phân(binary search)

Tìm kiếm nhị phân(binary search) là một thuật toán tìm kiếm xác định vị trí của một giá trị cần tìm trong một mảng đã được sắp xếp. Binary search chạy theo giời gian logarit trong trường hợp tệ nhất,

0 0 24

- vừa được xem lúc

LeetCode: Binary Search template chinh phục mọi problem

Chúc mừng năm mới. Đây là bài viết đầu tiên của mình nhân dịp năm Giáp Thìn, vì vậy mình cũng muốn viết về Thuật toán, vấn đề mà các bạn thường được hỏi đầu tiên khi đi phỏng vấn ở các công ty.

0 0 15

- vừa được xem lúc

Các bài viết ngắn phần 9

danang.fyi và repo danang-cuisine.

0 0 24

- vừa được xem lúc

The Solution of "Product of Array Except Self" under my thinking

This post is just my thinking of the solution for the famous coding problem which is a problem #238 posted in Leetcode in which you can refer from here. Actually I write this post to enhance my skill

0 0 31

- vừa được xem lúc

Leetcode problem #1: Find longest substring without repeating characters

Problem statement. For a given input string, return length of the longest substring in the given string without repeating characters. Examples:. Example1:.

0 0 32