首页 > 编程语言 >【算法】数组

【算法】数组

时间：2023-09-23 11:37:43浏览次数：31  
标签：right target nums int 算法 数组 left

1 数组理论基础

数组是存放在连续内存空间上的相同类型数据的集合。

  • 数组下标都是从0开始的
  • 数组内存空间的地址是连续的

在删除或者增添元素时，需要移动其他元素的地址：

C++要注意vector 和 array的区别，vector的底层实现是array，严格来讲vector是容器，不是数组。

数组的元素是不能删的，只能覆盖。

二维数组在内存的空间地址：

  • C++中二维数组在地址空间上是连续的

  • Java没有指针，不暴露元素的地址，寻址操作完全交给虚拟机

2 二分查找

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

示例1：

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4

示例2：

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1

提示：

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。

思路

有序数组、无重复元素 ⇒ 可以使用二分法

边界条件：根据区间定义来操作，遵循”循环不变量“规则

  1. 区间定义一：左闭右闭[left, right]
  • while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
  • if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            middle = left + (right - left) //2
            if nums[middle] > target:
                right = middle -1
            elif nums[middle] < target:
                left = middle + 1
            else:
                return middle
        return -1

时间复杂度：O(log n)，空间复杂度：O(1)

  1. 区间定义二：左闭右开[left, right)
  • while (left < right)，这里使用 < ，因为left == right在区间[left, right)是没有意义的
  • if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，即：下一个查询区间不会去比较nums[middle]

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)
        while left < right:
            middle = left + ((right - left) >> 1)
            if nums[middle] > target:
                right = middle
            elif nums[middle] < target:
                left = middle + 1
            else:
                return middle
        return -1

时间复杂度：O(log n)，空间复杂度：O(1)

3 移除元素

题目：

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]

示例2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]

说明：

请注意，输入数组是以**「引用」**方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

思路

1. 暴力解法，一个for循环遍历数组元素 ，第二个for循环更新数组

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        size,i = len(nums), 0
        while i < size:
            if nums[i] == val: # 发现需要移除的元素，就将数组集体向前移动一位
                for j in range(i+1, size): 
                    nums[j-1] = nums[j]
                size -= 1 # 此时数组的大小-1
                i -= 1 # 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
            i += 1
        return size

时间复杂度：O($n^2$)，空间复杂度：O(1)

2. 快慢双指针

  • 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
  • 慢指针：指向更新新数组下标的位置
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        fastIndex, slowIndex = 0, 0 # 快慢指针
        while fastIndex < len(nums):
             # slow 用来收集不等于 val 的值
            if nums[fastIndex] != val:
                nums[slowIndex] = nums[fastIndex]
                slowIndex += 1
            fastIndex += 1
        return slowIndex

时间复杂度：O(n)，空间复杂度：O(1)

3. 相向双指针方法，改变元素相对位置，数组中出现一个val，右指针左移一次

  • 如果左指针指向的元素等于 val，此时将右指针指向的元素复制到左指针的位置，然后右指针左移一位。重复直到左指针指向的元素的值不等于 val为止。当左指针和右指针重合的时候，左右指针遍历完数组中所有的元素。
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        left, right = 0, len(nums)
        while left < right:
            if nums[left] == val:
                nums[left] = nums[right -1]
                right -= 1
            else:
                left += 1
        return left

时间复杂度：O(n)，空间复杂度：O(1)

  • 只移动右边不等于val的元素
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        left, right = 0, len(nums)
        while left < right:
            if nums[left] == val: # 找左边等于val的元素
                while left < right and nums[right-1] == val: # 找右边不等于val的元素
                    right -= 1
                nums[left] = nums[right -1] # 将右边不等于val的元素覆盖左边等于val的元素
                right -= 1
            else:
                left += 1
        return left # left一定指向了最终数组末尾的下一个元素

4 有序数组的平方

题目：给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]

示例2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

思路

1. 暴力排序

class Solution:
    def sortedSquares(self, nums :List[int]) -> List[int]:
        for i in range(len(nums)):
            nums[i] *= nums[i]
        nums.sort()
        return nums

时间复杂度是 O(n + nlogn)， 可以说是O(nlogn)的时间复杂度，空间复杂度是O(1)

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        return sorted(x*x for x in nums)

2. 双指针

数组其实是有序的， 只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

class Solution:
    def sortedSquares(self, nums :List[int]) -> List[int]:
        idx = len(nums) - 1
        l, r, k = 0, idx, idx
        res = [0] * len(nums) # 需要提前定义列表，存放结果
        while l <= r:
            if nums[l] ** 2  < nums[r] ** 2: # 左右边界进行对比，找出最大值
                res[k] = nums[r] ** 2
                r -= 1
            else:
                res[k] = nums[l] **2
                l += 1
            k -= 1 # 存放结果的指针需要往前平移一位
        return res

时间复杂度O(n)，空间复杂度O(n)

5 长度最小的子数组**

题目：给定一个含有 n ****个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ****≥ target **的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。**如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

思路

1. 两个for循环暴力求解（会超时）

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        l = len(nums)
        minLen = float('inf')
        for i in range(l):
            sum = 0
            for j in range(i, l):
                sum += nums[j]
                if sum >= target:
                    minLen = min(minLen, j - i + 1)
                    break # 因为是找符合条件的最短子序列，一旦符合条件就break
        return 0 if minLen == float('inf') else minLen

时间复杂度：O($n^2$)，空间复杂度：O(1)

2. 滑动窗口（双指针），不断调节子序列的起始位置和终止位置，从而得出我们要想的结果

窗口就是满足其和 ≥ target 的长度最小的连续子数组。

窗口的起始位置如何移动：如果当前窗口的值大于target了，窗口就要向前移动了。

窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # 快慢指针代表#了滑动窗口起始位置
        slow, fast, l = 0, 0, len(nums)
        minLen = float('inf')
        sum = 0 # 滑动窗口数值之和
        while fast < l: 
            sum += nums[fast]
            while sum >= target:
                minLen = min(minLen, fast - slow + 1)
                sum -= nums[slow]  # 这里体现出滑动窗口的精髓之处，不断变更子序列的起始位置      
                slow += 1  
						fast += 1     
        return 0 if minLen == float('inf') else minLen

时间复杂度：O(n)，空间复杂度：O(1)

3. 前缀和+二分查找

为了使用二分查找，需要额外创建一个数组 sums 用于存储数组 nums 的前缀和。得到前缀和之后，对于每个开始下标 i，可通过二分查找得到大于或等于 i 的最小下标 bound，使 sums[bound]−sums[i]≥s，并更新子数组的最小长度。

这道题保证了数组中每个元素都为正，所以前缀和一定是递增的，这一点保证了二分的正确性。如果题目没有说明数组中每个元素都为正，这里就不能使用二分来查找这个位置了。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if not nums:
            return 0

    l = len(nums)
    minLen = float('inf')
    sums = [0]
    for i in range(l):
        sums.append(sums[-1] + nums[i]) # sums[i]代表nums[i]前面所有元素之和

    # l --- r     sum[r+1] - sum[l] &gt;= target
    # sum[r+1] &gt;= sum[l] + target
    for i in range(l):
        s = target + sums[i]
        bound = bisect.bisect_left(sums, s) # 二分查找sums里&ge;s的第一个位置
        if bound != len(sums): # sums没有比s大的（即没有符合条件
            minLen = min(minLen, bound - i)
            
    return 0 if minLen == float('inf') else minLen

6 螺旋矩阵

题目：给你一个正整数 n ，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

  • 1 <= n <= 20

思路

模拟顺时针画矩阵的过程：

  • 填充上行从左到右
  • 填充右列从上到下
  • 填充下行从右到左
  • 填充左列从下到上

注意边界条件！

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        ans = [[0] * n for _ in range(n)]
        l, r, t, b = 0, n - 1, 0, n - 1 # 左右上下边界
        curr = 1

    while curr &lt;= n**2:
        for i in range(l, r + 1): # 正在从左到右填充上行
            ans[t][i] = curr
            curr += 1
        t += 1

        for i in range(t, b + 1): # 正在从上到下填充下行
            ans[i][r] = curr
            curr += 1
        r -= 1

        for i in range(r, l - 1, -1): # 正在从右到左填充下行
            ans[b][i] = curr
            curr += 1
        b -= 1

        for i in range(b, t - 1, -1): # 正在从下到上填充左行
            ans[i][l] = curr
            curr += 1
        l += 1
        
    return ans

时间复杂度 O($n^2$):：模拟遍历二维矩阵的时间，空间复杂度 ：O($n^2$)

标签：right,target,nums,int,算法,数组,left
From： https://www.cnblogs.com/Aikoin/p/17724016.html

相关文章

  • 代码随想录算法训练营day17 | ● 110.平衡二叉树 ● 257. 二叉树的所有路径 ● 404.
    110.平衡二叉树classSolution{public:intgetHeight(TreeNode*node){if(node==NULL)return0;intleftHeight=getHeight(node->left);if(leftHeight==-1)return-1;intrightHeigh......
  • LZW字典压缩算法及例程
    字典压缩算法是一种数据压缩方法，其基本原理是将重复出现的字符串或者片段用一个短的代表符号来表示，从而减小数据的存储空间。字典压缩算法通常用于无损压缩数据。一种常见的字典压缩算法是Lempel-Ziv-Welch(LZW)算法。该算法通过构建和更新一个字典来实现压缩。初始时，字典中包含......
  • 【算法】算法性能分析
    1时间复杂度1.1知识点时间复杂度是一个函数，它定性描述该算法的运行时间。通常会估算算法的操作单元数量来代表程序消耗的时间。假设算法的问题规模为n，那么操作单元数量便用函数f(n)来表示，随着数据规模n的增大，算法执行时间的增长率和f(n)的增长率相同，这称作为算法的渐近时间复......
  • 【POJ 1521】Entropy 题解（贪心算法+优先队列+哈夫曼树）
    熵编码器是一种数据编码方法，通过对删除了“浪费”或“额外”信息的消息进行编码来实现无损数据压缩。换句话说，熵编码去除了最初不需要的信息，以准确编码消息。高度的熵意味着一条消息包含大量浪费的信息；以ASCII编码的英文文本是具有极高熵的消息类型的示例。已经压缩的消息，如JPEG图......
  • D 数组
    二分查找+优先队列先看要求：寻找r[i]值，使得在【i,r[i]】区间内数组A的和<=k[i]c[i],在【i,r[i]+1】数组A的和>k[i]c[i]，且r[i]的取值在[i-1,n]这个可以利用前缀和s数组来二分查找，寻找r[i]的值，利用函数upper_bounder(s+i,s+1+n,k[i]*c[i]+s[i-1])-s-1；然后看满意度：满意度为B数组中......
  • Kafka消息压缩算法性能调优与选择
    前言Kafka作为一款高性能的分布式消息队列，其消息压缩算法的选择和调优对于系统性能的提升至关重要。本文将深入探讨Kafka消息压缩算法的性能调优和选择。压缩算法的选择Kafka支持多种压缩算法，包括gzip、snappy和lz4。这些算法各有优缺点，需要根据实际情况进行选择。gzipgzip是......
  • 【数据结构】第四章 多维数组与广义表
    4.1数组的逻辑结构和基本运算数组可看成是一种特殊的线性表，其特殊在于，表中的数组元素本身也是一种线性表。在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其他复杂的结构更为简单。......
  • 计算机小白的成长历程——数组（2）
    大家好，很高兴又和大家见面啦！在上一篇我们介绍了一维数组的相关内容，今天咱们要介绍的是二维数组的相关内容。二维数组的创建和初始化1.二维数组的创建（1）什么是二维数组个人理解对于二维数组，我是这样理解的：一维就是一条线，二维就是一个面，那一维数组就是只有一行或者一列的数组，而二维数......
  • 数据结构之 - 深入了解数组数据结构
    数组是计算机科学中最基本且常用的数据结构之一。在本文中，我们将深入介绍数组的特性、操作以及在实际应用中的使用场景。通过全面了解数组，你将能够更好地理解它的原理和如何应用于解决问题。1.什么是数组？数组是一种线性数据结构，它由一系列相同类型的元素组成，这些元素被存储在连续......
  • JavaScript 终于原生支持数组分组了！
    在日常开发中，很多时候需要对数组进行分组，每次都要手写一个分组函数，或者使用lodash的groupBy函数。好消息是，JavaScript现在正在引入全新的分组方法：Object.groupBy和Map.groupBy，以后再也不需要手写分组函数了，目前最新版本的Chrome（117）已经支持了这两个方法！以前的数组分组假设有一......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99