23年暑假大一第一周编程练习

1.消失的数字：

def find_missing_number(nums):
    # 计算完整数组的和
    complete_sum = sum(range(1, len(nums) + 2))  # range包：[1,7)
    # print(complete_sum)       # 1+2+3+4+5+6=21
    # 计算数组中所有数的和
    array_sum = sum(nums)
    # print(array_sum)          # 1+2+4+5+6=18
    # 返回缺失的整数
    return complete_sum - array_sum

nums = [1, 2, 4, 5, 6]
print(find_missing_number(nums))  # 输出3

2.移除元素

def removeElement(nums, val):
    # 双指针
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1
    return (slow, nums)

nums = [0, 1, 2, 2, 3, 0, 4, 2]
val = 2
print(removeElement(nums, val))

3.合并两个有序数组

def merge(nums1, m, nums2, n):
    #nums1[m:]是nums1从索引m（即最后一个有效元素）到最后的部分
    #我们将nums2的全部元素赋值给nums1的这段部分
    nums1[m:] = nums2
    #然后我们对nums1进行排序
    nums1.sort()
    print(nums1)


nums1 = [1, 2, 3, 0, 0, 0]
m = 3
nums2 = [2, 5, 6]
n = 3
merge(nums1, m, nums2, n)

4.多数元素

def majorityElement(nums):
    count = 0
    candidate = None

    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1

    return candidate

# 示例用法
nums = [2, 2, 1, 1, 1, 2, 2]
majority_element = majorityElement(nums)
print(f"多数元素是：{majority_element}")

5.盛最多水的容器

def max_area(height):
    left = 0
    right = len(height) - 1
    max_area = 0

    while left < right:
        area = min(height[left], height[right]) * (right - left)
        max_area = max(max_area, area)

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_area
height = [1,8,6,2,5,4,8,3,7]
print(max_area(height))

6.搜索插入位置

def searchInsert(nums, target):
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        elif nums[mid] < target:
            left = mid + 1

        else:
            right = mid - 1

    # 当循环结束时，left 指针表示插入位置的索引
    return left

nums = [1,3,5,6]
target = 5

print(searchInsert(nums, target))

7.存在重复元素

def containsDuplicate(nums):
    num_set = set()

    for num in nums:
        if num in num_set:
            return True
        num_set.add(num)

    return False


nums = [1, 2, 3, 1]  # true
print(containsDuplicate(nums))
nums = [1, 2, 3, 4]  # false
print(containsDuplicate(nums))

8.数组中的第K个最大元素

import random


def findKthLargest(nums, k):
    left = 0
    right = len(nums) - 1

    while True:
        pivot_index = random.randint(left, right)
        pivot_position = partition(nums, left, right, pivot_index)

        if pivot_position == k - 1:
            return nums[pivot_position]

        elif pivot_position > k - 1:
            right = pivot_position - 1

        else:
            left = pivot_position + 1


def partition(nums, left, right, pivot_index):
    pivot_value = nums[pivot_index]
    nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
    store_index = left

    for i in range(left, right):
        if nums[i] > pivot_value:
            nums[i], nums[store_index] = nums[store_index], nums[i]
            store_index += 1

    nums[store_index], nums[right] = nums[right], nums[store_index]

    return store_index

nums = [3,2,1,5,6,4]
k = 2
print(findKthLargest(nums, k))