算法基础算法

下标映射

字数统计: 1.8k字   |   阅读时长: 8分
, ,

摘要: 下标映射的处理技巧

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

下标映射的处理技巧

本文来看一种数组中常见的操作 — 下标映射。

有两个数组 nums 和 result。其中 nums 是原数组，算法过程中需要对 nums 中的元素位置进行改变，而 result 就是算法过程中对 nums 中的元素位置改变后生成的新数组。并且新数组 result 跟原数组 nums 有某种下标映射关系：原数组的下标 i，对应新数组的下标 j。

注意这种映射可以理解为 [1, 2, …, n] 到自身的 n 阶置换，参考 组合数学5-群论。

算法的过程中可能会有两类需求:

(1) 给定原数组的下标 i，要知道它对应在新数组 result 的位置 j
(2) 给定新数组的下标 j，要追溯它对应在原数组 nums 中的下标 i

第(1)个是从 i 到 j；第 (2) 个是从 j 到 i。

对于(1)，我们定义一个下标映射函数 f：

1
j = f(i)

对于(2)，我们定义一个下标映射函数 indexes:

1
indexes(j) = i

它们之间满足关系 indexes(f(i)) = i。

324. 摆动排序 II

给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。

你可以假设所有输入数组都可以得到满足题目要求的结果。

提示：

1
2
3
1 <= nums.length <= 5e4
0 <= nums[i] <= 5000
题目数据保证，对于给定的输入 nums ，总能产生满足题目要求的结果

示例 1：
输入：nums = [1,5,1,1,6,4]
输出：[1,6,1,5,1,4]
解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。

示例 2：
输入：nums = [1,3,2,2,3,1]
输出：[2,3,1,3,1,2]

算法：下标映射

本题以前写过题解可以参考，文章链接: 三色排序。

本题正常的做法是先排序，得到中间数组 vec，然后按照题意，对排序后的数组做以下映射: 

1
2
偶数下标：用前半段，从大到小
奇数下标：用后半段，也从大到小

也就是以下映射关系：

上面的关系是从新数组下标 j 到原数组 i = indexes(j)，是前面提到的第(2)类需求。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        vector<int> vec(nums);
        sort(vec.begin(), vec.end());
        for(int j = 0; j < n; ++j)
            nums[j] = vec[indexes(n, j)];
    }

    int indexes(int n, int j)
    {
        if(j & 1)
            return n - 1 - (j - 1) / 2;
        else
            return (n - 1) / 2 - j / 2;
    }
};

算法(优化空间复杂度)

排序阶段直接在原坐标 i 映射后的坐标 f(i) 上运算。

首先我们根据前面的 indexes(j) 求出 f(i)：

然后实现排序，在枚举元素、划分区间的时候用原索引 i，而涉及元素操作，包括比较，交换等，用映射后的索引 f(i)。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        if(nums.empty()) return;
        int n = nums.size();
        if(n == 1) return;

        quicksort(nums);
    }

private:
    void quicksort(vector<int> &nums)
    {
        if(nums.empty()) 
            return;
        int n = nums.size();
        if(n == 1) 
            return;
        _quicksort3(nums, 0, n - 1);
    }

    // 快排最短模板, 不带 partition
    void _quicksort3(vector<int>& nums, int l, int r)
    {
        int n = nums.size();

        if(l >= r) 
            return;
        int i = l - 1, j = r + 1;
        int x = nums[f((l + r) >> 1, n)]; // pivot 取中间点的值已经很好了，随机更好
        while(i < j)
        {
            do j--; while(nums[f(j, n)] > x);
            do i++; while(nums[f(i, n)] < x);
            if(i < j) 
                swap(nums[f(i, n)], nums[f(j, n)]);
            else 
                _quicksort3(nums, l, j), _quicksort3(nums, j + 1, r); // 这一行代替了 partition
        }
    }

    int f(int i, int n) // 坐标映射
    {
        // 假id(做排序的id) -> 真实应该放到的 id
        // 偶数长度 3,7,2,6,1,5,0,4
        // 奇数数长度 4,8,3,7,2,6,1,5,0
        // i <= (n - 1)/2 的放下面, i >= (n - 1)/2 + 1 放上面
        if(i <= (n - 1) / 2)
            return 2 * ((n - 1) / 2 - i);
        else
            return 2 * (n - 1 - i) + 1;
    }
};

2164. 对奇偶下标分别排序

给你一个下标从 0 开始的整数数组 nums 。根据下述规则重排 nums 中的值：

(1) 按 非递增 顺序排列 nums 奇数下标 上的所有值。

  • 举个例子，如果排序前 nums = [4,1,2,3] ，对奇数下标的值排序后变为 [4,3,2,1] 。奇数下标 1 和 3 的值按照非递增顺序重排。

(2) 按 非递减 顺序排列 nums 偶数下标 上的所有值。

  • 举个例子，如果排序前 nums = [4,1,2,3] ，对偶数下标的值排序后变为 [2,1,4,3] 。偶数下标 0 和 2 的值按照非递减顺序重排。

返回重排 nums 的值之后形成的数组。

提示：

1
2
1 <= nums.length <= 100
1 <= nums[i] <= 100

示例 1：
输入：nums = [4,1,2,3]
输出：[2,3,4,1]
解释：
首先，按非递增顺序重排奇数下标（1 和 3）的值。
所以，nums 从 [4,1,2,3] 变为 [4,3,2,1] 。
然后，按非递减顺序重排偶数下标（0 和 2）的值。
所以，nums 从 [4,1,2,3] 变为 [2,3,4,1] 。
因此，重排之后形成的数组是 [2,3,4,1] 。

示例 2：
输入：nums = [2,1]
输出：[2,1]
解释：
由于只有一个奇数下标和一个偶数下标，所以不会发生重排。
形成的结果数组是 [2,1] ，和初始数组一样。

算法：下标映射

本题是 leetcode 第 279 场周赛的 A 题，周赛题解链接: leetcode第279场周赛。

首先将奇数位置的元素放到中间数组 A 中；偶数位置的元素放到中间数组 B 中。

对 A 从小到大排序，对 B 从大到小排序，然后用中间数组 A, B 组装新数组 result。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> sortEvenOdd(vector<int>& nums) {
        int n = nums.size();
        int na = (n + 1) / 2;
        int nb = n / 2;
        vector<int> A(na), B(nb);
        for(int i = 0; i < na; ++i)
            A[i] = nums[i * 2];
        for(int i = 0; i < nb; ++i)
            B[i] = nums[i * 2 + 1];
        sort(A.begin(), A.end());
        sort(B.begin(), B.end(), greater<int>());
        vector<int> result(n);
        for(int i = 0; i < n; ++i)
        {
            if(i & 1)
                result[i] = B[(i - 1) / 2];
            else
                result[i] = A[i / 2];
        }
        return result;
    }
};
Share