我想重复重新排列一个数组或std::vector，使最小值是第一个元素，最大值是最后一个元素，arr [(0+lastIdx)/2] 将是中位数，中位数之前的元素小于中位数，中位数之后的元素将更大。每次查询最小值、最大值和中值后，我都会对数据进行更改，我想再次快速查询这三个值。
每次我想重新排列数组时，数组都是具有相同大小的不同数组。
使用 std::nth_element 我可以在正确的位置获得中位数，然后我可以迭代数组以获得最小值和最大值。对于单个数组，这达到了 O(n) 复杂度，显然这无法改进。 (也许除了 O(n) 前面的复杂度常数)
我需要对一个数组进行操作，首先，我重新排列数组，然后做其他事情，这会使排列的数组再次完全没有排列，但没有插入新值。然后，我一遍又一遍地重复这个过程。
最佳答案
即使您以某种方式设法将定位最小值、最大值、中值的成本降低到零，
您仍然需要将错位的元素放在中位数以下或以上。这意味着最坏的情况 n/2 - 1 permutations每一次。
O(n) 时间，O(1) 空间)O(n) 时间，O(1) 空间)O(n) 时间，O(1) 空间)0 开始用于下方, 和上面的一个开始于 n-1 .而当前below元素在它应该在的位置，增加该索引。虽然当前 above元素在它应该在的位置，减少该索引。当发现放错位置的元素时，上下交换。重复只要below < above . (O(n) 时间，O(1) 空间)第 4、5 步的逻辑:当它们应该高于时低于中值的元素的数量正好是高于和应该低于的元素的数量。
当然，您可以在一个函数中合并传递 1、2、3，但这不会影响复杂性
让我们运行:
{3, 7, 9, 6, 8, 1, 4, 5, 2}
传递 1、2、3:min_pos = 5, max_pos = 2, median_pos = 7, median = 5
swap (0, min_pos) -> {1, 7, 9, 6, 8, 3, 4, 5, 2}
swap (9, max_pos) -> {1, 7, 2, 6, 8, 3, 4, 5, 9}
swap (4, median_pos) -> {1, 7, 2, 6, 5, 3, 4, 8, 9}
现在below_pos = 0 above_pos = 8 .元素没有错位。
下面的下一个错位是位置 1 的 7。下一个错位的上面是位置 6 的 4。
swap (1, 6) -> {1, 4, 2, 6, 5, 3, 7, 8, 9}
下面的下一个错位是位置 3 的 6。下一个错位的是位置 5 的 3。
swap (3, 5) -> {1, 4, 2, 3, 5, 6, 7, 8, 9}
算法输出
{1, 4, 2, 3, 5, 6, 7, 8, 9}
关于c++ - 我怎样才能重新排列数组以更快地获得最小值、中值和最大值？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29850560/
我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代
我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案 是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。 关于ruby-多次弹出/移动ruby数组，我们在StackOverflow上找到一
我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案 只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]
我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server
我正在使用puppet为ruby程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这
鉴于我有以下迁移:Sequel.migrationdoupdoalter_table:usersdoadd_column:is_admin,:default=>falseend#SequelrunsaDESCRIBEtablestatement,whenthemodelisloaded.#Atthispoint,itdoesnotknowthatusershaveais_adminflag.#Soitfails.@user=User.find(:email=>"admin@fancy-startup.example")@user.is_admin=true@user.save!ende
这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife
我正在使用active_admin，我在Rails3应用程序的应用程序中有一个目录管理，其中包含模型和页面的声明。时不时地我也有一个类，当那个类有一个常量时，就像这样:classFooBAR="bar"end然后，我在每个必须在我的Rails应用程序中重新加载一些代码的请求中收到此警告:/Users/pupeno/helloworld/app/admin/billing.rb:12:warning:alreadyinitializedconstantBAR知道发生了什么以及如何避免这些警告吗？ 最佳答案 在纯Ruby中:classA
这是一道面试题，我没有答对，但还是很好奇怎么解。你有N个人的大家庭，分别是1,2,3,...,N岁。你想给你的大家庭拍张照片。所有的家庭成员都排成一排。“我是家里的friend，建议家庭成员安排如下:”1岁的家庭成员坐在这一排的最左边。每两个坐在一起的家庭成员的年龄相差不得超过2岁。输入:整数N，1≤N≤55。输出:摄影师可以拍摄的照片数量。示例->输入:4，输出:4符合条件的数组:[1,2,3,4][1,2,4,3][1,3,2,4][1,3,4,2]另一个例子:输入:5输出:6符合条件的数组:[1,2,3,4,5][1,2,3,5,4][1,2,4,3,5][1,2,4,5,3][
我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat