本文最后更新于:2024年5月7日 下午

学而时习,本文记录排序操作相关算法练习笔记。

4. 寻找两个正序数组的中位数

题目描述

给定两个大小分别为 mn 的正序(从小到大)数组 nums1nums2。请你找出并返回这两个正序数组的 中位数

算法的时间复杂度应该为 O(log (m+n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution:
def findMedianSortedArrays(self, nums1, nums2) -> float:

if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1

MIN_NUM = int(-1e7)
MAX_NUM = int(1e7)
nums1 = [MIN_NUM] + nums1 + [MAX_NUM]
nums2 = [MIN_NUM] + nums2 + [MAX_NUM]

m = len(nums1)
n = len(nums2)

def get_index_2(index_1, m, n):
return (m+n-1) // 2 - index_1

def check_res(nums1, nums2, m, n, index_1, index_2):
if nums1[index_1 - 1] > nums2[index_2]:
return -1
if nums1[index_1] < nums2[index_2-1]:
return 1
return 0

low = 1
high = m-1
index_1 = (low + high) // 2 # 0 - m
index_2 = get_index_2(index_1, m, n)
res = check_res(nums1, nums2, m, n, index_1, index_2)

while res:
if res > 0:
low = index_1 + 1
else:
high = index_1 - 1

index_1 = (low + high) // 2
index_2 = get_index_2(index_1, m, n)

res = check_res(nums1, nums2, m, n, index_1, index_2)

if (m+n) %2 == 1:
return min(nums1[index_1], nums2[index_2])
else:
if nums1[index_1] < nums2[index_2]:
a = nums1[index_1]
index_1 += 1
else:
a = nums2[index_2]
index_2 += 1
b = min(nums1[index_1] , nums2[index_2])
return (a + b) / 2


452. 用最少数量的箭引爆气球

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中points[i] = [xstart, xend] 表示水平直径在 xstartxend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭,若有一个气球的直径的开始和结束坐标为 x``startx``end, 且满足 xstart ≤ x ≤ x``end,则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后,可以无限地前进。

给你一个数组 points返回引爆所有气球所必须射出的 最小 弓箭数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
points.sort(key=lambda x:x[0])
num = 0
cur_start = None
cur_end = None
for point in points:
if cur_start is None:
cur_start, cur_end = point
else:
new_start = max(cur_start, point[0])
new_end = min(cur_end, point[1])
if new_end >= new_start:
cur_start, cur_end = new_start, new_end
else:
num += 1
cur_start, cur_end = point
if cur_start is not None:
num += 1
return num

148. 排序链表

给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
data_list = []
p = head
while p:
data_list.append([p.val, p])
p = p.next

data_list.sort(key=lambda x:x[0])
fake_head = ListNode()
p = fake_head
for data in data_list:
p.next = data[1]
p = data[1]

p.next = None
return fake_head.next


文章链接:
https://www.zywvvd.com/notes/study/algorithm/sort/about-sort/


“觉得不错的话,给点打赏吧 ୧(๑•̀⌄•́๑)૭”

微信二维码

微信支付

支付宝二维码

支付宝支付

算法学习笔记 —— 排序
https://www.zywvvd.com/notes/study/algorithm/sort/about-sort/
作者
Yiwei Zhang
发布于
2020年5月21日
许可协议