左神算法、牛客网算法-初级2-3（python实现）

Gloria ·

更新时间:2024-09-21

· 987 次阅读

问题（荷兰国旗问题）

给定一个数组arr，和一个数num，请把小于num的数放在数组的
左边，等于num的数放在数组的中间，大于num的数放在数组的
右边。
要求额外空间复杂度O(1)，时间复杂度O(N)

def Nether_land_flag(arr,num):
    n = len(arr)
    less = -1
    more = n
    cur = 0
    while cur < more:
        if arr[cur]  num:
            # more， cur不用++
            more -= 1
            arr[more], arr[cur] = arr[cur], arr[more]
        else:
            cur += 1
    return arr
arr = [1,3,6,2,4,4,5]
num = 4
Nether_land_flag(arr,num)

[1, 3, 2, 4, 4, 5, 6]

快速排序

经典快排

def quick_sort(nums,first,last):
    if first >= last:
        return
    mid_value = nums[first]
    high = last
    low = first
    while low < high:
        while low = mid_value:
            high -= 1
        nums[low] = nums[high]
        while low < high and nums[low] < mid_value:
            low += 1
        nums[high] = nums[low]
    nums[low] = mid_value
    quick_sort(nums,first,low)
    quick_sort(nums,low+1,last)
arr = [1,3,6,2,4,4,5]
quick_sort(arr,0,len(arr)-1)
arr

[1, 2, 3, 4, 4, 5, 6]

改进快排(相等的值不用再次进行排序，加上随机选取需要排序的值)

import random

def Nether_land_flag(arr,first,last):
    less = first - 1
    more = last 
    cur = first
    random_index = random.randint(first,last)
    arr[random_index], arr[last] = arr[last], arr[random_index]
    num = arr[last]
    while cur < more:
        if arr[cur]  num:
            # more， cur不用++
            more -= 1
            arr[more], arr[cur] = arr[cur], arr[more]
        else:
            cur += 1
    arr[last], arr[more] = arr[more], arr[last]
    # 返回 小于num 的第一个下标，和大于num的第一个下标
    return less + 1, more
def re_quick_sort(nums,first,last):
    if first < last:
        p = Nether_land_flag(nums,first,last)
        re_quick_sort(nums,first,p[0]-1)
        re_quick_sort(nums,p[1]+1,last)

nums = [1,3,2,4,5,7,8,4,3,4]
last = len(nums) - 1
re_quick_sort(nums,0,last)
nums

[1, 2, 3, 3, 4, 4, 4, 5, 7, 8]

堆排序

i 的左节点 2i+1 右节点 2i+2 父节点 (i-1)//2
heapify 自顶向下一个值变小下沉操作（大根堆）(本身是大根堆)

def heapify(arr,i,heapsize):
    # 堆的大小个数
    left = 2 * i + 1
    while left < heapsize:
        max_index = i
        right = left + 1
        if left < heapsize and arr[max_index] < arr[left]:
            max_index = left
        if right < heapsize and arr[max_index] < arr[right]:
            max_index = right
        if i != max_index:
            arr[i], arr[max_index] = arr[max_index], arr[i]
            i = max_index
            left = 2 * i + 1
        else:
            break

heap_insert 自底向上

# 底部插入一个数，如果是最大，则推至堆顶
def heap_insert(arr,i):
    while arr[i] > arr[(i-1) // 2]:
        arr[i], arr[(i-1) // 2] = arr[(i-1) // 2], arr[i]
        i = (i-1) // 2
        if i <= 0:
            break

def heap_sort(arr):
    n = len(arr)
    if n  0:
        heapify(arr,0,heap_size)
        arr[0], arr[heap_size-1] = arr[heap_size-1], arr[0]
        heap_size -= 1

nums = [3,4,5,6,7,8,9,9,15]
n = len(nums)
# for i in range(0,n):
#     heap_insert(nums,i)
heap_sort(nums)
nums

[3, 4, 5, 6, 7, 8, 9, 9, 15]

桶排序

给定一个数组，求如果排序之后，相邻两数的最大差值，要求时
间复杂度O(N)，且要求不能用非基于比较的排序。

def gap(nums):
    n = len(nums)
    if n <= 1:
        return 0
    for i in range(n):
        if i == 0:
            max_num = nums[i]
            min_num = nums[i]
        max_num = max(nums[i], max_num)
        min_num = min(nums[i], min_num)
    if max_num == min_num:
        return 0
    hash_num = [False for i in range(n+1)]
    mins = [None for i in range(n+1)]
    maxs = [None for i in range(n+1)]
    for i in range(n):
        bid = bucket(nums[i],n,min_num,max_num)
        mins[bid] = min(mins[bid], nums[i]) if hash_num[bid] else nums[i]
        maxs[bid] = max(maxs[bid], nums[i]) if hash_num[bid] else nums[i]
        hash_num[bid] = True
    print(hash_num)
    print(mins)
    print(maxs)
    lastmax = maxs[0]
    res = 0
    for i in range(n+1):
        if hash_num[i]:
            res = max(res , mins[i] - lastmax)
            lastmax = maxs[i]
    return res
def bucket(num, length, min_num, max_num):
    return int(length * (num - min_num)/(max_num - min_num))

nums = [5,10,2,7,8,8,9,10,7,8]
gap(nums)

[True, False, False, True, False, False, True, True, True, False, True]
[2, None, None, 5, None, None, 7, 8, 9, None, 10]
[2, None, None, 5, None, None, 7, 8, 9, None, 10]
3

栈结构

class stack():
    def __init__(self,size=0):
        self.stack = []
        self.size = size
    def stack_pop(self):
        if self.stack != []:
            return self.stack.pop()
        else:
            return False
    def stack_peek(self):
        if self.stack != []:
            return self.stack[-1]
        else:
            return False
    def stack_push(self,num):
        if len(self.stack) < self.size:
            self.stack.append(num)
        else:
            return False

队列

class Queue():
    def __init__(self,size=0):
        self.queue = []
        self.size = size
    def queue_pop(self):
        if self.queue != []:
            return self.queue.pop(0)
        else:
            return False
    def queue_push(self,num):
        if len(self.queue) < self.size:
            self.queue.append(num)
        else:
            return False

实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

【要求】
1.pop、push、getMin操作的时间复杂度都是0（1）。
2.设计的栈类型可以使用现成的栈结构。

class stack():
    def __init__(self,size=0):
        self.stack = []
        self.size = size
        self.min_list = []
    def stack_pop(self):
        if self.stack != []:
            self.min_list.pop()
            return self.stack.pop()
        else:
            return False
    def stack_peek(self):
        if self.stack != []:
            return self.stack[-1]
        else:
            return False
    def stack_push(self,num):
        if len(self.stack) < self.size:
            if self.stack == []:
                self.stack.append(num)
                self.min_list.append(num)
            else:
                self.stack.append(num)
                if num < self.min_list[-1]:
                    self.min_list.append(num)
                else:
                    self.min_list.append(self.min_list[-1])
        else:
            return False
    def get_min(self):
        if self.min_list != []:
            return self.stack[-1]
        else:
            return False

如何仅用队列结构实现栈结构？
如何仅用栈结构实现队列结构？

class Queue_Stack():
    # queue -> stack
    def __init__(self):
        self.data = []
        self.helper = []
    def re_push(self,num):
        self.data.append(num)
    def re_pop(self):
        if not self.data:
            return False
        while self.data != []:
            tmp = self.data.pop(0)
            if self.data == []:
                break
            self.helper.append(tmp)
        self.data, self.helper = self.helper, self.data
        return tmp

class Stack_Queue():
    # stack -> queue
    def __init__(self):
        self.push_queue = []
        self.pop_queue = []
    def re_push(self,num):
        self.push_queue.append(num)
    def re_pop(self):
        if self.pop_queue == []:
            if self.push_queue == []:
                return False
            else:
                while self.push_queue:
                    self.pop_queue.append(self.push_queue.pop())
        return self.pop_queue.pop()