代码随想录62——额外题目【数组】：189轮转数组、724寻找数组的中心下标、922按奇偶排序数组II

1.189轮转数组

参考：代码随想录，189轮转数组；力扣题目链接

1.1.题目

1.2.解答

这道题目在字符串里其实很常见，我把字符串反转相关的题目列一下：

字符串：力扣541.反转字符串II、字符串：力扣151.翻转字符串里的单词、字符串：剑指Offer58-II.左旋转字符串

本题其实和字符串：剑指Offer58-II.左旋转字符串 就非常像了，剑指offer上左旋转，本题是右旋转。

注意题目要求是要求使用空间复杂度为 O(1) 的 原地 算法

原地左边旋转字符串：

• 反转区间为前n的子串
• 反转区间为n到末尾的子串
• 反转整个字符串

原地右边旋转字符串：

• 反转整个字符串
• 反转区间为前k的子串
• 反转区间为k到末尾的子串

需要注意的是，本题还有一个小陷阱，题目输入中，如果k大于nums.size了应该怎么办？

其实移动到num.size()次数之后就相当于没有移动，所以直接执行k % nums.size()次数就行。

最后给出代码如下，注意是右旋转，所以要先旋转整个字符串，再旋转子串。

void rotate(vector<int> &nums, int k)
{
    k = k % nums.size();   // 防止k过大

    // 左移：先旋转子串，再旋转整个字符串；右移：先旋转子串，再旋转整个字符串
    reverse(nums.begin(), nums.end());          // 先旋转整个数组
    reverse(nums.begin(), nums.begin() + k);    // 在旋转前半部分
    reverse(nums.begin() + k, nums.end());  // 最后旋转后半部分
}
1
2
3
4
5
6
7
8
9

2.724寻找数组的中心下标

参考：代码随想录，724寻找数组的中心下标；力扣题目链接

2.1.题目

2.2.解答

首先注意不要把这道题目理解错了，其中说的左右相等的下标是不包括当前的数字的，而是不算当前数字，其左边的数字和右边的数字的和相等。

但是这道题目仍然非常简单：

• 遍历一遍求出总和sum
• 遍历第二遍求中心索引左半和leftSum
  同时根据sum和leftSum 计算中心索引右半和rightSum
  判断leftSum和rightSum是否相同

给出代码如下：

int pivotIndex(vector<int> &nums)
{
    // 1.统计和
    int sum = 0;
    for(const auto& num : nums)
        sum += num;
    
    int left_sum = 0;
    int right_sum = 0;
    // 2.遍历求左边的和 和 右边的和
    for(int i = 0; i < nums.size(); i++)
    {
        // 注意这个并不是真的left_sum，而是多加了nums[i]
        left_sum += nums[i];  
        // 所以这里right_sum就也要把nums[i]加上
        right_sum = sum - left_sum + nums[i];  
        if(left_sum == right_sum)
            return i;
    }

    // 运行到这里说明没找到，返回-1
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

注意：上述代码就是在计算过程中，遍历到当前的下标时，直接把左边的left_sum也加上了当前的nums[i]，此时i右边的数字综合是sum - left_sum。但是由于我们的left_sum多加了nums[i]，所以这里计算right_sum的时候也要多加nums[i]，即right_sum = sum - left_sum + nums[i]。比如1 7 3 6 5 6的例子，便利到6的时候，左边和是11，但是此时left_sum = 17，因为多加了当前的6；此时右边和是11，所以也要多加上当前的6，结果也是17.

另外一个方法其实就是可以便利到当前数字之后，就从总和中减去当前的数字，然后再/2，看结果和左边的和是否相等。此时的代码如下：

int pivotIndex(vector<int> &nums)
{   
    // 1.计算总和
    int sum = 0;
    for(const auto& num : nums)
        sum += num;

    int left_sum = 0;   // 左边总和，不包括当前下标
    for(int i = 0; i < nums.size(); i++)
    {
        // 如果此时总和/2等于左边的和
        if(left_sum * 2 == sum - nums[i])   
            return i;
        else 
            left_sum += nums[i];   // 否则累加当前数字，给下一次准备
    }

    // 运行到这里说明没找到，返回-1
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.922按奇偶排序数组II

参考：代码随想录，922按奇偶排序数组II；力扣题目链接

3.1.题目

3.2.解答

这道题目直接的想法可能是两层for循环再加上used数组表示使用过的元素，这样的的时间复杂度是O(n^2)。

但是其实可以换一个角度想，建立一个结果数组，分别分成奇数索引的空位和偶数索引的空位。然后遍历原数组中的元素，如果是奇数，那么就填到奇数空位中；如果是偶数，就填到偶数索引的空位中，这样就很简单了。

直接给出代码如下：

vector<int> sortArrayByParityII(vector<int> &nums)
{
    vector<int> result(nums.size(), 0);   // 先构造存储结果的数组
    int odd_idx = 1;   // 初始化奇数和偶数索引
    int even_idx = 0;   

    for(const auto& num : nums)
    {
        if(num % 2 == 0)   // 偶数
        {
            result[even_idx] = num;
            even_idx += 2;
        }
        else   // 奇数
        {
            result[odd_idx] = num;
            odd_idx += 2;
        }
    }

    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22