数组入门（一）

1、leetcode704二分查找

题目描述

题目描述：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例1：

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例2：

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

题解：

1、二分查找

二分查找的核心思想是 每次都将搜索范围缩小一半：

  1. 计算中间索引mid，比较nums[mid]和target:
    • 若nums[mid]==target，则找到目标值，返回索引。
    • 若nums[mid]>target，则目标值应该在mid左侧，缩小范围right=mid-1。
    • 若nums[mid]<target，则目标值应该在mid右侧，缩小范围left=mid+1。
  2. 重复以上步骤，直到left>right，则返回-1，表示找到。

2、代码实现

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left,right=0,len(nums)-1
        while left<=right: # 使用<=以确保所有可能的值都会被检查
            mid=(left+right)//2
            if nums[mid]==target:
                return mid
            elif nums[mid]<target:
                left=mid+1 # mid 已经检查过，所以移动到mid+1
            else:
                right=mid-1
        return -1 # 没找到返回-1

解释：

  • 采用while循环，确保left==right也能检查最后一个元素。
  • 计算mid时用(left+right)//2，避免整数溢出。（py中无需考虑）
  • 通过left=mid+1和right=mid-1,二分缩小范围

3、为什么while left<=right?

如果while left<right:

  • 可能会漏最后一个元素(left==right时不检查)。
  • 可能出现死循环(当left不能推进时)

示例：

nums=[1,3,5,7,9]
target=9

正确写法:

Step left right mid nums[mid] 结果
1 0 4 2 6 target>5,left=3
2 3 4 3 7 target>7,left=4
3 4 4 4 9 找到，返回4

错误写法：

Step left right mid nums[mid] 结果
1 0 4 2 5 target>5,left=3
2 3 4 3 7 target>7,left=3(死循环)

二分查找的时间复杂度分析

  • 最坏情况：每次搜索范围小一半，O(log n)
  • 最优情况：目标一开始被找到，O(1)
  • 平均情况：大约O(log n)

2、leetcode27移除元素

题目描述

题目描述：

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

  • 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
  • 返回 k。

示例1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

题解

方法1:暴力清除

class Solution(object):
   def removeElement(self, nums, val):
       """
       :type nums: List[int]
       :type val: int
       :rtype: int
       """
       while val in nums:
           nums.remove(val)
       return len(nums)

如果val在nums里面，就清除，最后返回剩余nums的长度

==时间复杂度==：O(n)

==空间复杂度==：O(1)

方法2：双指针

class Solution:
   def removeElement(self, nums, val):
       slow = 0
       for x in nums:
           if x != val:
               nums[slow] = x
               slow += 1
       return slow

如果不等于val赋值给慢指针所在的位置

==时间复杂度==：O(n)

==空间复杂度==：O(1)

总结：

这道题相对比较简单，新手掌握python语法的可以练练，并熟悉双指针的写法，以后会经常用到。