算法练习-有序数组平方(思路+流程图+代码)

发布时间:2024年01月17日

难度参考

????????难度:简单

????????分类:数组

????????难度与分类由我所参与的培训课程提供,但需要注意的是,难度与分类仅供参考。以下内容均为个人笔记,旨在督促自己认真学习。

题目

????????给你一个按非递减顺序(即递增)排序的整数数组 nums,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。

????????示例1:

????????输入:nums=[-4,-1,0,3,10]

????????输出:[0,1,9,16,100]

????????解释:平方后,数组变为[16,1,0,9,100], 排序后,数组变为[0,1,9,16,100]

????????示例2:

????????输入:nums=[-7,-3,2,3,11]

????????输出:[4,9,9,49,121]

????????额外要求: 请你设计时间复杂度为O(n)的算法解决本问题

思路

????????这个问题的关键是将按非递减顺序排序的整数数组的元素平方后,按非递减顺序存储在新数组中。要解决这个问题,可以使用双指针的方法,时间复杂度为O(n)。

????????以下是解决问题的思路和步骤:

  1. 创建一个新的整数数组,用于存储平方后的结果。
  2. 使用两个指针,一个指向原始数组的最小值,另一个指向最大值。
  3. 初始化一个索引变量,从新数组的末尾开始填充。
  4. 进入一个循环,直到左指针大于等于右指针。
  5. 在循环中,计算左指针元素的平方和右指针元素的平方。
  6. 比较左平方和右平方的大小。
  7. 如果左平方大于等于右平方,将左平方值存入新数组,并移动左指针向右。
  8. 否则,将右平方值存入新数组,并移动右指针向左。
  9. 每次循环结束后,将新数组的索引位置向前移动。
  10. 循环结束后,新数组中存储了平方后的结果,并且按非递减顺序排序。
  11. 返回新数组作为结果。

????????这个算法的关键点在于使用双指针,从原数组的两端向中间移动,根据平方值的大小选择左指针或右指针的值放入新数组。这样可以确保新数组中的值按非递减顺序排序。这个算法的时间复杂度是O(n),因为只需要一次遍历原数组。

示例

????????理解这个算法可能会有些抽象,以下我将尝试提供更具体的步骤和示例来帮助你更好地理解:

????????假设我们有一个按非递减顺序排序的整数数组 nums,如下所示:

nums = [-4, -1, 0, 3, 10]

????????我们首先创建一个新的数组 result,用于存储平方后的结果,与 nums 数组的大小相同:

result = [0, 0, 0, 0, 0]

????????接下来,我们使用两个指针,一个指向 nums 数组的最小值(最左边的元素 -4),另一个指向 nums 数组的最大值(最右边的元素 10)。还有一个索引变量 index 初始化为新数组的最后一个位置(4)。

left = 0 right = 4 index = 4

????????然后,我们进入一个循环,直到 left 指针大于 right 指针。在循环中,我们执行以下步骤:

  1. 计算 left 指针元素的平方(例如,(-4) * (-4) = 16)。

  2. 计算 right 指针元素的平方(例如,10 * 10 = 100)。

  3. 比较左平方和右平方的大小。

    • 如果左平方大于等于右平方,将左平方值(16)存入 result 数组的 index 位置,然后将 left 指针向右移动一位。
    • 否则,将右平方值(100)存入 result 数组的 index 位置,然后将 right 指针向左移动一位。
  4. 每次循环结束后,index 向前移动一位。

????????重复以上步骤,直到 left 指针大于等于 right 指针。最终,result 数组将包含平方后的结果,按非递减顺序排序。

result = [0, 1, 9, 16, 100]

????????这个算法的关键是根据平方值的大小选择 left 指针或 right 指针的值放入 result 数组,并同时移动相应的指针。这样可以确保 result 数组中的值按非递减顺序排序。

梳理

?????????这种算法之所以能够实现按非递减顺序排序平方后的数组,是因为原始数组 nums 已经按非递减顺序排序。这个算法利用了两个指针,一个从数组的最小值开始,另一个从数组的最大值开始,然后向中间移动。下面解释为什么这个算法有效:

  1. 原始数组已排序: 由于原始数组 nums 已经按非递减顺序排序,因此数组中的元素可以分为负数和非负数两部分,其中非负数部分的平方值是递增的。这一点很关键,因为平方后的值仍然保持非递减顺序。

  2. 使用两个指针: 算法使用两个指针,一个指向原始数组的最小值(负数部分的开头),另一个指向最大值(非负数部分的结尾)。这两个指针向中间移动,保证了我们能够同时考虑到负数和非负数部分的平方值。

  3. 比较平方值大小: 在每一步中,算法比较了左指针元素的平方值和右指针元素的平方值,然后选择较大的平方值存储在新数组中。这个选择是为了确保新数组中的值按非递减顺序排序。

  4. 指针移动: 根据比较的结果,如果左平方值较大,那么左指针向右移动;如果右平方值较大,那么右指针向左移动。这样在每一步都选择了当前范围内的最大平方值,并将其放入新数组中。

  5. 索引递减: 为了确保新数组中的值按非递减顺序排序,使用一个索引变量从新数组的末尾向前移动。这确保了新数组中的较大平方值被放在正确的位置。

????????这个算法的本质是通过双指针,分别从原数组的两端向中间移动,每次选择当前指针所指元素的平方值中较大的一个,然后逆序填充到新数组中,从而得到按非递减顺序排序的平方结果。

????????总结来说,这个算法通过合理的双指针移动和平方值比较,充分利用了原始数组已排序的性质,使得新数组中的值按非递减顺序排序。这是一种非常高效的方法,时间复杂度为O(n)。

代码

#include <cmath>      // 包含C++标准库中的cmath头文件,用于平方操作
#include <iostream>   // 包含C++标准库中的iostream头文件,用于输入输出
#include <vector>     // 包含C++标准库中的vector头文件,用于使用向量容器
using namespace std;  // 使用C++标准库的std命名空间

vector<int> sortedSquares(vector<int>& nums) {
    int n = nums.size();    // 获取输入数组的大小
    vector<int> result(n);  // 创建一个新的整数向量,用于存储平方后的结果
    int left = 0, right = n - 1;  // 初始化左右指针,分别指向数组的第一个和最后一个元素
    int index = n - 1;  // 从新数组的末尾开始填充
    
    while (left <= right) {  // 进入循环,直到左指针大于右指针
        int left_square = pow(nums[left], 2);  // 计算左指针元素的平方
        int right_square = pow(nums[right], 2);  // 计算右指针元素的平方
        
        if (left_square >= right_square) {  // 如果左平方大于等于右平方
            result[index] = left_square;  // 将左平方值存入新数组
            left++;  // 移动左指针向右
        } else {
            result[index] = right_square;  // 否则,将右平方值存入新数组
            right--;  // 移动右指针向左
        }
        
        index--;  // 移动新数组的索引位置向前
    }
    
    return result;  // 返回存储平方结果的新数组
}

int main() {
    vector<int> nums = {-4, -1, 0, 3, 10};  // 输入的整数数组
    vector<int> result = sortedSquares(nums);  // 调用函数得到平方结果
    
    for (int i = 0; i < result.size(); i++) {  // 遍历并输出结果
        cout << result[i] << " ";
    }
    
    return 0;  // 返回程序的退出码
}

????????时间复杂度:O(n)
????????空间复杂度:O(n), 其中n为nums数组的长度,且辅助数组的长度为n。

打卡

????????懒得布置环境,Acwing的A+B题目永远的神!

文章来源:https://blog.csdn.net/qq_54813250/article/details/135631538
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。