作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我想编写一个程序,生成一个数组到另一个数组的交换元素的步骤,(例如:从{0,1,2}到{0,2,1},步骤是1<->2,表示交换元素1和元素2的位置),以A={0,1,3,2}和B={2,0,3,1}为例,我原来的概念是这样的:
这是我试过的代码:
#include <stdlib.h>
#include <functional>
#include <vector>
int main(){
std::function<bool(int,int)> f=[](int a,int b){
if(a>=b)
printf("%d<->%d\n",a,b);
return a<b;
};
std::vector<int> a={0,1,3,2};
std::sort(a.begin(),a.end(),f);
printf("---\n");
std::vector<int> b={2,0,3,1};
std::sort(b.begin(),b.end(),f);
return 0;
}
输出:
1<->0 //step to sort A
3<->1
2<->1
---
3<->0 //step to sort B
3<->2
1<->0
所以从 0,1,3,2 到 2,0,3,1 的步长应该是:
1<->0
3<->1
2<->1
1<->0
3<->2
3<->0
但是当我按照步骤操作时:
0,1,3,2
1,0,3,2
3,0,1,2
3,0,2,1
3,1,2,0
2,1,3,0
2,1,0,3
结果是 2,1,0,3 而不是 2,0,3,1,为什么?我生成步骤的概念是错误的吗?如果是这样,是否有其他方法可以生成通过交换位置将数组更改为另一个数组的步骤?
最佳答案
问题是每次比较时您都打印“交换”,并且两个值的顺序不正确,这可能是不正确的,std::sort
算法可以在不交换的情况下进行检查。您可以使用自定义 Int
要测试的结构:
struct Int {
Int(int v) : v_(v) { }
Int(const Int&) = default;
Int& operator=(const Int& o) {
std::cout << v_ << " <- " << o.v_ << '\n';
v_ = o.v_;
return *this;
}
int v_;
};
bool operator<(const Int& lhs, const Int& rhs) {
return lhs.v_ < rhs.v_;
}
然后:
int main(){
std::vector<Int> a{0,1,3,2};
std::cout << "Sorting A:\n";
std::sort(a.begin(),a.end());
std::cout << '\n';
std::vector<Int> b={2,0,3,1};
std::cout << "Sorting B:\n";
std::sort(b.begin(),b.end());
return 0;
}
输出是:
Sorting A: Sorting B:
1 <- 1 0 <- 2
3 <- 3 2 <- 0
2 <- 3 3 <- 3
3 <- 2 1 <- 3
3 <- 2
2 <- 1
它为您提供了各种分配 - 请注意 std::sort
实现可能会针对如此小的范围进行优化,这意味着您不仅可以进行交换(例如,在上面,对于 B
,您可以“一起”交换 1、2 和 3)。
所以你需要做的是(没有无用的 a <- a
):
2 <-> 3
2 -> 1
3 -> 2
1 -> 3
0 <-> 2
然后你只需要在二进制交换中转换它:
2 <-> 3
2 <-> 1
1 <-> 3
0 <-> 2
如果你想直接获得二进制交换,你可以变得更难看(希望你的计算机对这个 UB 温和)并且:
struct Int {
Int(int v) : v_(v) { }
Int(const Int&) = default;
Int& operator=(const Int& o) {
if (v_ != o.v_)
std::cout << v_ << " <-> " << o.v_ << '\n';
std::swap(v_, o.v_);
return *this;
}
mutable int v_;
};
输出:
Sorting A: Sorting B:
2 <-> 3 0 <-> 2
1 <-> 3
1 <-> 2
合并:
2 <-> 3
1 <-> 2
1 <-> 3
0 <-> 2
关于c++ - 如何生成通过交换元素(例如 : from {0, 1,2} 到 {0,2,1})将数组更改为另一个数组的步骤?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39993907/
我是一名优秀的程序员,十分优秀!