关注并标星 3分钟秒懂大数据

每天1次，打卡阅读

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

第2天：双指针

1、Leetcode 977. 有序数组的平方

1、题目介绍：

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

2、示例如下：

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、复杂度分析

2、Leetcode 189. 旋转数组

1、题目介绍：

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

2、示例如下：

3、解题思路：

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

1 1 1 1 1 2 2 2

后移3位

2 2 2 1 1 1 1 1

我们可以使用额外的数组来将每个元素放至正确的位置。用 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、复杂度分析

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

End

最近整理了一份计算机类的书籍，包含python、java、大数据、人工智能、算法等，种类特别齐全。

获取方式：关注公众号：3分钟秒懂大数据，回复：福利，就可以获得这份超级大礼！，小伙伴们快来领取吧。

点个在看你最好看

ITPub博客

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

最新文章