我有几个std::vector,全长相同.我想对这些向量中的一个进行排序,并将相同的变换应用于所有其他向量.这样做有一个简洁的方法吗？(最好使用STL或Boost)？一些向量包含ints,其中一些包含std::strings.
伪代码:
std::vector<int> Index = { 3, 1, 2 };
std::vector<std::string> Values = { "Third", "First", "Second" };
Transformation = sort(Index);
Index is now { 1, 2, 3};
... magic happens as Transformation is applied to Values ...
Values are now { "First", "Second", "Third" };
我们给出了两个小写拉丁字母字母序列.它们的长度相同,并且具有相同数量的给定类型的字母(第一个具有与第二个相同数量的t,依此类推).我们需要找到将第一个序列转换为第二个序列所需的最小交换次数(通过"交换",我们的意思是改变两个相邻字母的顺序).我们可以安全地假设每两个序列可以相互转换.我们可以用蛮力做到这一点,但序列太长了.
输入:
序列的长度(至少2,最多999999),然后是两个序列.输出:
一个整数,表示序列变为相同所需的交换数.示例:
{5,aaaaa,aaaaa}应输出{0},
{4,abcd,acdb}应输出{2}.
我想到的第一件事是bubblesort.我们可以简单地对每个交换的序列进行计数.问题是:a)它是O(n ^ 2)最坏情况b)我不相信它会给我每个案例的最小数字......即使是优化的bubblesort似乎也没有做到这一点.我们可以实施鸡尾酒种类来解决海龟的问题 - 但它会给我最好的表现吗？或者也许有更简单/更快的东西？
这个问题也可以表述为:当允许的唯一操作是换位时,我们如何确定两个字符串之间的编辑距离？
我这里的代码有两个数组.它对arr []进行排序,因此最高值将在索引0中.现在第二个数组arr1 []包含字符串,我希望代码将arr []所做的任何更改应用于arr1 [].因此arr [0]将返回6,而arr1 [0]将返回字符串"d1".请注意"d1"与6的索引是否相同？排序后我想要相同的值仍然有他们的字符串对应物.
我该怎么做呢？
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
int arr[ 5 ] = { 4, 1, 3, 6, 2 };
string arr1[ 5 ] = { "a1", "b1", "c1", "d1", "e1" };
std::sort( arr, arr + 5, std::greater< int >() );
cout << arr[0] << arr1[0] << endl; …