【小算法】两个 vector，对其中一个排序，另一个位置对应变化

问题

做算法题时需要的一个子步骤，有两个 std::vector，对其中的一个进行从大到小排序，另外一个的位置对应改变

解决方法

假设两个 std::vector v1, v2;

• 法1:使用 multimap（执行时间长，占内存大）

  std::multimap<int, int, std::greater<int>> m; // val, pos
  for (int i = 0; i < v1.size(); i++) {
    m.insert({v1[i], i});
  }
  // 遍历
  for (auto &it : m) {
    std::cout << v1[it.second] << ", " << v2[it.second] << std::endl;
  }
1
2
3
4
5
6
7
8

• 法2: 使用 vector (GPT3.5 给出算法，执行时间最短，占内存较优)

  std::vector<std::pair<int, int>> vv;
  for (int i = 0; i < v1.size(); i++) {
    vv.emplace_back(std::make_pair(v1[i], v2[i]));
  }

  std::sort(vv.begin(), vv.end(),
            [](const std::pair<int, int> &a, const std::pair<int, int> &b) {
              return a.first > b.first;
            });

  for (auto &it : vv) {
    std::cout << it.first << ", " << it.second << std::endl;
  }
1
2
3
4
5
6
7
8
9
10
11
12
13

• 法3: 测试将 vector 换成 vector (比 multimap 性能还要差)

  std::vector<std::vector<int>> vv;
  for (int i = 0; i < v1.size(); i++) {
    vv.emplace_back(std::vector{v1[i], v2[i]});
  }

  std::sort(vv.begin(), vv.end(),
            [](const std::vector<int> &a, const std::vector<int> &b) {
              return a[0]> b[0];
            });

  for (auto &it : vv) {
    std::cout << it[0]<< ", " << it[1]<< std::endl;
  }
1
2
3
4
5
6
7
8
9
10
11
12
13

• 法4：新姿势：直接对下标排序（某题解截取，执行时间较优，占内存最小）
  用到了一个 iota 函数，这个是一个希腊字母的读音，C++11 标准引入

  std::vector<int> pos(v1.size());
  std::iota(pos.begin(), pos.end(), 0); // 从 0 开始递增，调用 operator++ 方法
  std::sort(pos.begin(), pos.end(), // 这个快排很巧妙，使用值的大小对下标进行排序
            [&](int i, int j) { return v1[i] > v1[j]; }); // 注意这里会用到下标，所以 pos 数组初始化不能从 1 开始

  for (auto i : pos) {
    std::cout << v1[i] << ", " << v2[i] << std::endl;
  }
1
2
3
4
5
6
7
8