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))