我正在尝试使用“分而治之”方法找到数组的最小值。
为此,我曾想过逐行排序矩阵,以便稍后找到它的最小值,但我有一个问题:
我的矩阵定义为map<int, map<int, int> >
and,当试图应用STL的sort()函数时,它给了我一个错误。
我的代码是这样的:
for(int i = start; i < end; i++){
sort(matrix[i].begin(), matrix[i].end());
}
我想将该行分配给一个向量以便能够执行该函数,但我不知道该怎么做。
如果这种转换无法完成,我也有兴趣找到另一种方法来获得最小值。
有没有一种有效的方法可以用这种方法找到数组的最小值?
由于映射按键而不是按值排序,并且您的键是数组的索引,因此您别无选择,只能执行线性搜索。您无法排序,因为
map
s 无法重新排序,因为您破坏了 s 本身map
试图保护的顺序关系,因此编译器错误。此外,如果您可以(使用另一种数据结构)进行排序以找到最小值,那也是低效的。订购的成本总是比一个一个的搜索要高。当你需要排序的值不止一件事时,你需要排序。所以:这比使用
std::sort
或您能想到的任何其他机制更有效。可能还有其他更有效的解决方案,但这完全取决于您为什么用map
s 表示数组或为什么要对元素进行排序。您必须将数组的所有元素复制到一维数组中,如下所示:
他
arregloTotal
拥有你数组的所有元素最后,将 std::map 更改为定义大小的 std::vector,牺牲灵活性和空间以方便算法。
要获得最小值,请逐行应用 std::sort() ,然后循环比较第一列,直到获得最小值。
而且,为了知道次要对应的位置 (x,y),我生成了原始矩阵的副本并遍历与最小值对应的行,直到找到给定值。
这样,x 为行号,y 为列号。