算法学习笔记 —— 排序

本文最后更新于：2024年1月14日晚上

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

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

题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

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

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] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

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

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

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 ，请将其按升序排列并返回 排序后的链表 。

# 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