三个月算法进阶--day2

2020-08-25 约 442 字预计阅读 1 分钟次阅读

小记

leetcode第四题，按题号顺序遇到的第一个困难题，编程初学者也可以尝试，感觉不需要什么知识铺垫，谨慎想过一遍就能落笔。

先掌握一般情况

想个简单的实例，理清操作顺序

边界情况较复杂最后考虑

写完主体写边界

降低时间复杂度，引入变量或更复杂的数据结构来存储中间值、临时值

动态标记，动态存储，最后收集结果

写完仍需谨慎检查

模拟仿真

复杂的更现实的问题，抽象出类来模拟仿真，顺一遍也许就能得到答案。约瑟夫环的问题就可用队列来模拟，出队再进队是关键。

Python中列表

列表是一种操作几乎不受限的数据结构，只需取其中几个操作便可模拟栈与队列，只是操作的时间复杂度未必高效，主要是因为列表在非尾端的插入和删除都是O(n)的。

记录

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        length1 = len(nums1)
        length2 = len(nums2)
        total_length = length1 + length2
        flag = total_length // 2 + 1
        if not nums1:
            if length2 % 2 == 0:
                return (nums2[flag-2] + nums2[flag-1]) / 2
            else:
                return nums2[flag-1]
        if not nums2:
            if length1 % 2 == 0:
                return (nums1[flag-2] + nums1[flag-1]) / 2
            else:
                return nums1[flag-1]
        temp = []
        pot1 = 0
        pot2 = 0
        start = 0
        while (pot1 <= length1 - 1 or pot2 <= length2 - 1) and start != flag:
            if pot1 == length1:
                temp.append(nums2[pot2])
                pot2 += 1
            elif pot2 == length2:
                temp.append(nums1[pot1])
                pot1 += 1
            elif nums1[pot1] <= nums2[pot2]:
                temp.append(nums1[pot1])
                pot1 += 1
            else:
                temp.append(nums2[pot2])
                pot2 += 1
            start += 1
        if total_length % 2 == 0:
            return sum(temp[-2:]) / 2
        else:
            return temp[-1]

目录