14天算法入门-第2天-双指针

秒速五厘米 2022-09-04 13:46 241阅读 0赞

关注并标星微信公众号

**3分钟秒懂大数据**

每天1次，打卡阅读

获取AI大数据技术、面经、内推信息

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODIwMTkzNg_size_16_color_FFFFFF_t_70][]

![20210814111750541.png][]

**1、题目介绍：****  **

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

**2、示例如下：**

![图片][17b810d9dcd0ee28a7cf63104f669473.png]

**3、解题思路：**

我们可以使用两个指针分别指向位置 0 和 n-1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况，读者可以仔细思考其精髓所在。

**4、代码如下**：

（1）JAVA版本

class Solution {
           public int[] sortedSquares(int[] nums) {
               int n = nums.length;        int[] ans = new int[n];        for (int i = 0, j = n - 1, pos = n - 1; i <= j;) {
                   if (nums[i] * nums[i] > nums[j] * nums[j]) {
                       ans[pos] = nums[i] * nums[i];                ++i;            } else {
                       ans[pos] = nums[j] * nums[j];                --j;            }            --pos;        }        return ans;    }}

（2）Python版本

class Solution:    def sortedSquares(self, nums: List[int]) -> List[int]:        n = len(nums)        ans = [0] * n               i, j, pos = 0, n - 1, n - 1        while i <= j:            if nums[i] * nums[i] > nums[j] * nums[j]:                ans[pos] = nums[i] * nums[i]                i += 1            else:                ans[pos] = nums[j] * nums[j]                j -= 1            pos -= 1                return ans

5、复杂度分析

![图片][bcd4e66d2a45128d489f3008626e1719.png]

![20210814111821748.png][]

**1、题目介绍：  **

给定一个数组，将数组中的元素向右移动 `k`* *个位置，其中 `k`* *是非负数。

**2、示例如下：**

![图片][1fecd04c80cb3f17deb7566db1725d2d.png]

**3、解题思路：**

说是旋转数组，实际上不过是把数组看成一个环，然后给每一位都沿着同一方向移动几个位数

1 1 1 1 1 2 2 2

后移3位

2 2 2 1 1 1 1 1

![图片][46895b7252730858086e506c834fb8af.png]

我们可以使用额外的数组来将每个元素放至正确的位置。用 n表示数组的长度，我们遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i+k) mod n 的位置，最后将新数组拷贝至原数组即可。

**4、代码如下：**

（1）JAVA版本

class Solution {
           public void rotate(int[] nums, int k) {
               int n = nums.length;        int[] newArr = new int[n];        for (int i = 0; i < n; ++i) {
                   newArr[(i + k) % n] = nums[i];        }        System.arraycopy(newArr, 0, nums, 0, n);    }}

（2）C++版本

class Solution {
       public:    void rotate(vector<int>& nums, int k) {
               int n = nums.size();        vector<int> newArr(n);        for (int i = 0; i < n; ++i) {
                   newArr[(i + k) % n] = nums[i];        }        nums.assign(newArr.begin(), newArr.end());    }};

**5、复杂度分析**

![图片][24a9d0c430725fb0d9a4affd60a61581.png]

**以上就是****14天算法入门-第2天-双指针****讲解内容！觉得好的，点赞，在看，分享三连击，谢谢！！！**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODIwMTkzNg_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODIwMTkzNg_size_16_color_FFFFFF_t_70]: /images/20220829/48e949eccc7c4ed1b1d668443b67dac5.png
[20210814111750541.png]: /images/20220829/978f596171334632a4139606074f39db.png
[17b810d9dcd0ee28a7cf63104f669473.png]: /images/20220829/3672be51f0d640f89424364b9517a6cc.png
[bcd4e66d2a45128d489f3008626e1719.png]: /images/20220829/f5d55a8e07084c2d83ca88fe47049b1d.png
[20210814111821748.png]: /images/20220829/0f0cbbaf71984b7581cfa5dede59f4a5.png
[1fecd04c80cb3f17deb7566db1725d2d.png]: /images/20220829/7329303ad90b4fc39a5666405188e13c.png
[46895b7252730858086e506c834fb8af.png]: /images/20220829/4eef93447b9647d8ba0fb56f0562d575.png
[24a9d0c430725fb0d9a4affd60a61581.png]: /images/20220829/59a227651e574599b9d1f044122b14db.png