对于一项作业，我需要解决一个数学问题我把范围缩小到：
设A[1, ... ,n]为n整数的数组。
设y为整数常量。
现在，我必须编写一个算法，在M(y)时间内找到O(n)的最小值：M(y) = Sum |A[i] - y|, i = 1 to n。注意，我不只是取A[i] - y，而是取绝对值|A[i] - y|。
为了清楚起见，我还把这个方程放在Wolfram Alpha中。
我考虑过最小二乘法，但我认为这不会产生最小值M(y)，而会产生更大的平均值A。由于我取的是A[i] - y的绝对值，因此也无法将此函数区分为y另外，我不能只是想出任何算法，因为我必须在O(n)时间内完成另外，我相信在某些情况下，y会有更正确的答案，在这种情况下，y的值必须等于A的整数元素之一。
这真的让我吃了整整一个星期了，我还没弄明白。有谁能教我怎么走，或者给我指出正确的方向吗？我卡住了。非常感谢你的帮助。
最佳答案
你想选择一个y，其中M(y) = sum(abs(A[i] - y))是最小的。假设每个A[i]都是正的（它不会改变结果，因为问题通过转换是不变的）。
让我们从两个简单的观察开始首先，如果选择y使其y < min(A)或y > max(A)，则M（y）的值将大于选择y使其min(A) <= y <= max(A)的值此外，a（m（y）是凸的，存在唯一的局部极小值或极小值的范围。
所以我们可以从在区间内选取一些y开始，试着移动这个值，得到一个更小的M（y）为了使事情更容易理解，让我们在[min(A) .. max(A)]中对A排序并选择i（所以[1 .. n]）。
有三种情况需要考虑。
如果{n是奇数且y = A[i]}或{n是偶数且A[i+1] > A[i]}，则i < (n+1)/2。
这是因为，从i < n/2到M(A[i+1]) < M(A[i])，减少的项数（即M(A[i])）大于增加的项数（即M(A[i+1])），并且增加或减少的项数始终相同。在n是奇数的情况下，n-i，因为2*i是偶数（因此必然小于我们从中减去1的较大偶数）。
在更正式的术语中，i，其中s和g表示这样的索引i < (n+1)/2 <=> 2*i < n+1 <=> 2*i < n和M(A[i]) = sum(A[i]-A[s]) + sum(A[g]-A[i])。所以如果A[s] < A[i]，那么A[g] > A[i]。因为A[i+1] > A[i]和M(A[i+1]) = sum(A[i]-A[s]) + i*(A[i+1]-A[i]) + sum(A[g]-A[i]) - (n-i)*(A[i+1]-A[i]) = M(A[i]) + (2*i-n)*(A[i+1]-A[i])，2*i < n，所以A[i+1] > A[i]。
类似地，如果{n是奇数且(2*i-n)*(A[i+1]-A[i]) < 0}，或者{n是偶数且M(A[i+1]) < M(A[i])}，则A[i-1] < A[i]。
最后，如果{n是奇数且i > (n+1)/2}或{n是偶数且i > (n/2)+1}，则有一个最小值，因为递减或递增，我最终将分别引导到第一种或第二种情况。对于i还有剩余的可能值，但所有这些值都会导致i也是最小值。
A的中值正好是A[i]的值，在这里我满足最后一个条件如果a中的元素数是奇数，则正好有一个这样的值，M(A[i-1]) > M(A[i])（但可能有多个索引）；如果它是偶数，则有一个这样的值的范围（可能只包含一个整数），i = (n+1)/2。
有一个标准的C++算法，可以帮助你找到O（n）时间的中位数：nth_element。如果您使用的是另一种语言，请查找the median of medians algorithm（nico schertlerpointed out）甚至introselect（这是nth_element通常使用的语言）。
关于arrays - 求A [i]与常数之差的最小和，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39756662/