第二天——双指针

977.有序数组的平方

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

我的思路算比较暴力的

完全没有体现双指针

而是简单平方后直接冒泡了

有一说一我觉得这个非递减的描述是有问题的

按照给出的参考案例来说实际上就是升序

我寻思乱序不也包含在非递减里吗

public class Solution {
    public int[] SortedSquares(int[] nums) {
        int[] numsquare = new int[nums.Length];

        for(int i = 0; i<nums.Length ; i++)
        {
            numsquare[i] = nums[i]*nums[i];
        }

        for(int i = 0; i<numsquare.Length; i++)
        {
            for(int j=0; j<numsquare.Length-1-i; j++)
            {
                if(numsquare[j]>numsquare[j+1])
                {
                    int temp = numsquare[j];
                    numsquare[j] = numsquare[j+1];
                    numsquare[j+1] = temp;
                }
            }
        }

        return numsquare;
    }
}

接下来正儿八经讲讲双指针

这道题的关键在于原本的数组它是升序排列的

存在几种情况

1.所有元素都是非负数,根本就不用排序

2.元素中存在负数,且存在某一负数的绝对值比正数来得大

那么我们可以这么想

我们每次都拿两边的最值来进行比较

因为原本的数组是升序排列,假设长度为n

我们取的就是第0个和第n-1个

假如最大值的平方比最小值的平方来得大

那么这个数的平方就是新数组的最大值

把这个数放到新数组的最后一位

以此类推,我们来比较最小值的平方和倒数第二个的平方

然后把大的那个平方数放到新数组的倒数第二位

重复过程

最后就能将原数组的平方升序排列了

public class Solution {
    public int[] SortedSquares(int[] nums) 
    {
        int n = nums.Length;
        int[] numsquare = new int[n];

        for(int i=0, j=n-1, k=n-1; i<=j;)
        {
            int left = nums[i]*nums[i];
            int right = nums[j]*nums[j];
            if(left < right)
            {
                numsquare[k] = right;
                j--;
            }
            else
            {
                numsquare[k] = left;
                i++;
            }
            k--;
        }

        return numsquare;
    }
}

189.旋转数组

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

进阶:

尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?

方法一:额外数组分配

要注意的是这里的思路

不是简单的后几个元素先放到新数组

要注意它移动的是位置

好好看看他给的样例

我在这里踩了三次坑

第一次:

我简单的认为是第k+1个索引之后元素的都先放到新数组里

很快啊我就发现当长度为偶数个的时候放的是k而不是k+1

第二次:

我觉得应该是n-k个,我就很高兴的发现我又错了

假如长度为1呢?所以我加了判断长度为1的时候不做任何处理

第三次:

问题又来了,长度为2,它要移动三个位置,你怎么写呢?

到这里我终于意识到我的思路错了

实际上应该是把数直接分配而不是考虑转移

原数组下标为i的元素移动了k个位置对吧

那新数组的位置就是i+k

根据第三次踩的坑要注意k>n的情况

所以最后确定的索引就是(i+k)%n

public class Solution {
    public void Rotate(int[] nums, int k)
    {
        int n = nums.Length;
        int[] resort = new int[n];
        for(int i=0; i<n; i++)
        {
            resort[(i+k)%n] = nums[i];
        }

        for(int i=0;i<n; i++)
        {
            nums[i] = resort[i];
        }
    }
}

//11.3更新

今天感觉状态还行,来看看所谓双指针的解法

方法二:环状替换

相当于上一种不用新数组的变体

虽然不用新数组但是用了一个int值来暂时存储

大致过程如下,定义一个存储交换元素值的temp和一个被交换元素的索引x

一开始我们就让temp等于第0个元素,需要移动到第(0+k)%n的位置上

那么这个位置x的元素就要和temp的值交换

然后我们再看这个位置x的元素,同样用temp存储

重复上一步交换元素的值

以此类推把所有的值遍历一遍

关键在于要判断什么时候应该退出循环

官方的题解推导的有点迷,简单来说就是n和k的最大公约数

但是你每一次计数一次,确定次数为n也可以推出循环

总之这种思路理解起来有难度

我到现在也是半知半解的

public class Solution {

    public int gcd(int a,int b)
    {
        if(b == 0)
        {
            return a;
        }
        return gcd(b,a%b);
    }
    
    public void Rotate(int[] nums, int k) {
        int n = nums.Length;
        k = k % n;//考虑k>n的情况先进行处理
        int count = gcd(k,n);
        
        for(int i=0;i<count;i++)
        {
            int temp = i;
            int prev = nums[temp];

            do
            {
                int next = (temp+k)%n;
                int change = nums[next];
                nums[next] = prev;
                prev = change;
                temp = next;
            }
            while(i != temp);
        }
    }
}

方法三:数组翻转

等脑子冷静会再来

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注