算法

C++算法题-排列奇数

题目

codewar 题目链接

You will be given an array of numbers. You have to sort the odd numbers in ascending order while leaving the even numbers at their original positions.
Examples
[7, 1] => [1, 7]
[5, 8, 6, 3, 4] => [3, 8, 6, 5, 4]
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0] => [1, 8, 3, 6, 5, 4, 7, 2, 9, 0]

题目非常简单，就是将数组出现的奇数用升序重新排列，而偶数就放着不动。

1
2
3
4
5
6
7
8

class Kata
{
public:
    std::vector<int> sortArray(std::vector<int> array)
    {
        return array;
    }
};

个人题解

需要处理一段数组然后返回去，很显然少不了遍历。而单独对奇数处理并排序那肯定需要单列出来处理。
因而，我首先想到的是声明一个数组单独存放奇数，并对该数组排序。后续还需要再写入原数组。那么就需要标记出来原数组的奇数元素。一开始我是这样干的，不过到后面发现奇数元素特征其实就是 %2 == 1，而 1 又是 C++ 的真，因而实际连判断是否相等都不用写，遇到 %2 结果为一的就可以执行。
那么首先用 for 语句遍历填充奇数数组，并排序:

1
2
3
4
5
6
7
8
9

std::vector<int> sortArray(std::vector<int> array) {
    std::vector<int> odd;

    for (auto it : array) {
        if (it % 2) {
            odd.emplace_back(it);
        }
        std::sort(odd.begin(), odd.end());
}

这样 odd 就已经排序好了， 后面也是再遍历一遍 array 把 array 的奇数项按排序好的 odd 数组顺序替换便可。需要注意的是迭代器的变量不是数组元素，其为复制过来的，因而无法使用迭代器循环来处理，还是使用三段式吧。

1
2
3
4
5
6
7
8
9

    int j = 0;
    for (int i = 0; i < array.size(); i++) {
        if (array[i] % 2){
            array[i] = odd[j++];
        }
    }

    return array;
}

综合下来代码是:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <algorithm>
#include <vector>

class Kata {
   public:
    std::vector<int> sortArray(std::vector<int> array) {
        std::vector<int> odd;

        for (auto it : array) {
            if (it % 2) {
                odd.emplace_back(it);
            }
            std::sort(odd.begin(), odd.end());
        }
        int j = 0;
        for (int i = 0; i < array.size(); i++) {
            if (array[i] % 2){
                array[i] = odd[j++];
            }
        }

        return array;
    }
};

他人解答

一、std::copy_if() 算法库

看起来实际上很简单，其实很好做。会不会觉得我其实是水博客？但是当我看到 sloutions 的 std::copy_if() 就完成我处理 odd 数组的整个过程时候，我被震撼了……
这是他的答案:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <algorithm>

class Kata
{
public:
    std::vector<int> sortArray(std::vector<int> array)
    {
        std::vector<int> odds;
        std::copy_if(array.begin(), array.end(), std::back_inserter(odds), [] (int x) {return x % 2;});
        std::sort(odds.begin(), odds.end());
        for (int i = 0, j = 0; i < array.size(); i++) if (array[i] % 2) array[i] = odds[j++];
        return array;
    }
};

他用了 c++ <algorithm> 库里面的 copy_if() 函数而且用了 lambda 表达式来处理，这样的方式实在是巧妙简单。
首先需要搞懂的是这个函数:

1

std::copy_if(array.begin(), array.end(), std::back_inserter(odds), [] (int x) { return x % 2; });

前两个参数不需要多解释，那么看到第三个参数：

  • back_inserter(odds) 这段是将匹配的元素插入到 odds 的后面，相当于 odds.emplace_back(it)
  • [](int x){x % 2;} 一段简单的 lambda 表达式将遍历的 array 元素作为 x 进行判断，如果是奇数就输出 1，而是就是 true,可以插入到 odds，如果偶数就是 0，为 false 遍历下一个。

后面排序插入的代码就和我写的一样了，不再解释。
主要要研究 copy_if() 的使用:
首先是 std::copy() 函数:

1

std::copy(II first, II last, OI result)

前两个指向源容器要复制的头尾，最后一个是输入容器的开始位置。
那么 copy_if() 可以说是增强版 copy() 使用 lambda 表达式进行判断使得复制更加灵活。

1

std::copy_if(IIter, IIter, OIter, Predicate)

前三个参数一样，而最后一个 Predicate ，可以用 lambda 表达式，这个参数要接收的是布尔类型变量。

二、位运算

我们可以将 % 2 替换为 &1
&1 会仅保留最低位，其可能为 0 或 1，而如果是奇数那么最低位是 1，如果是偶数最低为 0,这样的作用和 % 2 一样，而且位运算会更快。

十进制 二进制 &1
0 0000 0
1 0001 1
2 0010 0
3 0011 1
5 0101 1
8 1110 0

也就是说，当我们使用 if (array[i] % 2) 时，可以换成 if (array[i] &1)，这同样执行的是判断奇偶数。

萌ICP备20241614号