什么是最小缓冲区值，以便整数数组按递增顺序排序？

Problem: Given an array of integers, find the minimum buffer value such that the array can be sorted in strictly increasing order. Each element in the array can add or subtract up to the buffer value.

问题:给定一个整数数组,找到最小缓冲区值,以便可以按严格递增的顺序对数组进行排序。数组中的每个元素都可以添加或减去缓冲区值。

Ex: [4, 0, 9, -2]

The minimum buffer value is 6, because you can change the array into:

最小缓冲区值为6,因为您可以将数组更改为:

[4 - (6 or 5 or 4 or 3), 0 + (-1 or 0 or 1 or 2), 9 - (6) = 3, -2 + (6) = 4]

I believe I have a solution that works O(N^2), but I'm wondering if I can do better.

我相信我有一个适用于O(N ^ 2)的解决方案,但我想知道我是否可以做得更好。

EDIT: never mind, my solution doesn't work.

编辑:没关系,我的解决方案不起作用。

My solution:

For each element, draw a line with slope 1 passing that element. Find the smallest buffer value that allows every element to be shifted onto the line. Keep track of the buffer values obtained and return the smallest one at the end.

对于每个元素,绘制一条通过该元素的斜率为1的线。找到允许每个元素移位到线上的最小缓冲区值。跟踪获得的缓冲区值,并在最后返回最小的缓冲区值。

Thanks

4 个解决方案

#1

O(n) can be achieved by looping the array one by one and keeping the invariant correct and keeping track of the current buffer size:

O(n)可以通过逐个循环数组并保持不变量正确并跟踪当前缓冲区大小来实现:

1. we start from left and go one by one to the right

我们从左边开始,一个接一个地走到右边

2. a single element subarray is by definition sorted

根据定义,单个元素子阵列被排序

3. adjust the current element using our current buffer to the lowest possible value (so the invariant still holds)

使用当前缓冲区将当前元素调整到最低可能值(因此不变量仍然保持不变)

4. if current element (after adjustment) is bigger than the previous element then we do not need to do anything (sorted)

如果当前元素(调整后)大于前一个元素,那么我们不需要做任何事情(已排序)

5. otherwise (unsorted) we need to update the buffer (increase it) - this is done trivially by checking the difference in the current element and the max of the already sorted array which is simply the previous element ( so we add abs((curr-prev)/2) + 1 to the current buffer) and the previous/current values (to the smallest values possible). At this point we don't need to care about earlier entries because since we are increasing the buffer to decrease the previous/current values we could simply subtract up to abs((curr-prev)/2) + 1 from each previous value and the invariant would hold.

否则(未排序)我们需要更新缓冲区(增加它) - 这通过检查当前元素的差异和已经排序的数组的最大值来完成,这只是前一个元素(所以我们添加abs((curr-) prev)/ 2)+ 1到当前缓冲区)和前一个/当前值(到可能的最小值)。此时我们不需要关心先前的条目,因为我们正在增加缓冲区以减少先前/当前值,我们可以简单地从每个先前的值中减去abs((curr-prev)/ 2)+ 1并且不变量会持有。

Some examples to make it all more clear (bolded - current, italic - previous):

一些例子使它更清晰(粗体 - 当前,斜体 - 以前):

I) Input: [4, 0, 9, -2]

I)输入:[4,0,9,-2]

• [4] - sorted by definition

[4] - 按定义排序

• [4,0] - unsorted, update current one with buffer [4,0], diff = (4-0)/2+1 = 3 => [1,2], buffer = 3 // the update is done as follow: decrease the previous value by the whole diff, for the current one check if newPrevious (1 here) plus 1 is in range current+-diff, if yes then set newPrevious+1, otherwise set current+diff

[4,0] - 未排序,用缓冲区[4,0]更新当前值,diff =(4-0)/ 2 + 1 = 3 => [1,2],缓冲区= 3 //更新完成为follow:将前一个值减去整个diff,对于当前的一个检查newPrevious(1 here)加1是否在范围current + -diff中,如果是,则设置newPrevious + 1,否则设置current + diff

• [1,2,9] - sorted, update current one with buffer [1,2,6] // here update is done similarly to the previous update but instead off doing current+diff we do current-diff

[1,2,9] - 排序,用缓冲区更新当前的一个[1,2,6] //这里更新与前一个更新类似,但是关闭当前+ diff我们做current-diff

• [1,2,6,-2] - unsorted, update current one with buffer [1,2,6,1], still unsorted so diff = (6-1)/2+1 = 3, buffer = 6, [1,2,3,4]

[1,2,6,-2] - 未排序,用缓冲区[1,2,6,1]更新当前的一个,仍未排序,因此diff =(6-1)/ 2 + 1 = 3,缓冲区= 6,[ 1,2,3,4]

Done, buffer = 6

完成,缓冲区= 6

II) Input: [40, 31, 140, 131]

II)输入:[40,31,140,​​131]

• [40] - sorted by definition

[40] - 按定义排序

• [40,31] - unsorted, update current one with buffer [40,31], diff = (40-31)/2+1=5 => [35,36], buffer = 5

[40,31] - 未排序,用缓冲区更新当前的[40,31],diff =(40-31)/ 2 + 1 = 5 => [35,36],缓冲区= 5

• [35,36,140] - sorted, update current one [35,36,135]

[35,36,140] - 排序,更新当前的[35,36,135]

• [35,36,135,131] - unsorted, update current one [35,36,135,136]

[35,36,135,131] - 未分类,更新当前的[35,36,135,136]

Done, buffer = 5

完成,缓冲区= 5

III) Input: [1,1,1,1]

III)输入:[1,1,1,1]

• [1] - sorted by definition

[1] - 按定义排序

• [1,1] - unsorted, update current one [1,1], diff = (1-1)/2+1=1 => [0,1] (because 0+1 is ok), buffer = 1

[1,1] - 未排序,更新当前一个[1,1],diff =(1-1)/ 2 + 1 = 1 => [0,1](因为0 + 1没问题),缓冲区= 1

• [0,1,1] - unsorted, update current one [0,1,2], sorted

[0,1,1] - 未排序,更新当前一个[0,1,2],已排序

• [0,1,2,1] - unsorted, update current one [0,1,2,2], diff = (2-2)/2+1=1 => [0,1,2,3], buffer = 2

[0,1,2,1] - 未排序,更新当前一个[0,1,2,2],diff =(2-2)/ 2 + 1 = 1 => [0,1,2,3],缓冲区= 2

Done, buffer = 2

完成,缓冲区= 2

IV) Input: [7,11,1,2,3]

IV)输入:[7,11,1,2,3]

• [7] - sorted by definition

[7] - 按定义排序

• [7,11] - sorted, adjust [7,11]

[7,11] - 排序,调整[7,11]

• [7,11,1] - unsorted, adjust [7,11,1], diff = (11-1)/2+1 = 6 => [7,5,6], buffer = 6
  • here we can see that we do not need to check anything before 11 as all the previous numbers are smaller than 11 so if we do 11 - X we could simply do PREVIOUS - X and the invariant would still hold

  在这里我们可以看到我们不需要在11之前检查任何东西,因为之前的所有数字都小于11所以如果我们做11 - X我们可以简单地做上一个 - X并且不变量仍然会保持

[7,11,1] - 未分类,调整[7,11,1],差异=(11-1)/ 2 + 1 = 6 => [7,5,6],缓冲区= 6这里我们可以看到我们不需要在11之前检查任何东西,因为之前的所有数字都小于11,所以如果我们做11 - X我们可以简单地做PREVIOUS - X并且不变量仍然会保持

• [7,5,6,2] - unsorted, adjust [7,5,6,7] <- invariant still holds, I simply didn't adjust the first 7 in the previous step

[7,5,6,2] - 未分类,调整[7,5,6,7] < - 不变仍然保持,我根本没有调整上一步中的前7

• [7,5,6,7,3] - unsorted, adjust [7,5,6,7,8]

[7,5,6,7,3] - 未分类,调整[7,5,6,7,8]

Done, buffer = 6

完成,缓冲区= 6

V) Input: [0,1,3,-15]

V)输入:[0,1,3,-15]

Up until [0,1,3] nothing changed

直到[0,1,3]没有任何改变

• [0,1,3,-15] diff = 10, adjust prev and current [0,1,-7,-6] - again here we can see that we increase the buffer from 0 to 10 so all numbers to the left of 3 and 3 itself can be decreased by 10 and the invariant will hold but for the rest of the algorithm we don't need to do this

[0,1,3,-15] diff = 10,调整prev和current [0,1,-7,-6] - 再次在这里我们可以看到我们将缓冲区从0增加到10所以所有数字都在左边3和3本身可以减少10并且不变量将保持但是对于算法的其余部分我们不需要这样做

Done, buffer = 10

完成,缓冲区= 10

VI) Input: [1,2,3,4]

VI)输入:[1,2,3,4]

• [1] - sorted by definiton

[1] - 按定义排序

• [1,2] - sorted, adjust by buffer 0

[1,2] - 排序,按缓冲区0调整

• [1,2,3] - sorted, adjust by buffer 0

[1,2,3] - 排序,按缓冲区0调整

• [1,2,3,4] - sorted, adjust by buffer 0

[1,2,3,4] - 排序,按缓冲区0调整

Done, buffer = 0

完成,缓冲区= 0

#2

The original answer

原来的答案

My original answer consisted of the following three steps. That algorithm works provided that the max value in the normalized array comes before the min value in the normalized array. The sample arrays that I was considering were [4, 0, 9, -2] and [0, 1, 3, -15]. Note that in both of those sample arrays, the max precedes the min. However, this algorithm fails if the absolute min in the array appears before the absolute max. Two examples where the algorithm fails are [-15, 1] and [40, 31, 140, 131].

我原来的答案包括以下三个步骤。该算法可用,前提是规范化数组中的最大值位于规范化数组中的最小值之前。我考虑的样本数组是[4,0,9,-2]和[0,1,3,-15]。请注意,在这两个示例数组中,最大值都在min之前。但是,如果数组中的绝对最小值出现在绝对最大值之前,则此算法将失败。算法失败的两个例子是[-15,1]和[40,31,140,​​131]。

Step 1: subtract the array index from the value at that index

第1步:从该索引处的值中减去数组索引

array:              4    0   9   -2
index:             -0   -1  -2   -3
                   ----------------
normalized array:   4   -1   7   -5

Step 2: scan the normalized array to find the min and max values

步骤2:扫描规范化数组以查找最小值和最大值

max =  7
min = -5

Step 3: subtract the min from the max and divide by 2 (rounding up if necessary) and there's your answer

第3步:从最大值中减去min并除以2(必要时向上舍入),这就是你的答案

(7 - (-5)) / 2 = 6

The rationale and flaw in the original answer

原答案的基本原理和缺陷

The idea behind my original answer was that the midpoint between the max and the min provided a target value that every entry in the normalized array could be adjusted to hit. The max and min being the farthest from the target required the largest adjustments and hence provided the answer. However, after seeing hk6279's comment, I realized that it's possible to have multiple targets for the normalized array. For example, consider the array [40, 31, 140, 131]. The first step is

我最初的答案背后的想法是,最大值和最小值之间的中点提供了一个目标值,规范化数组中的每个条目都可以调整为命中。离目标最远的最大值和最小值需要最大的调整,因此提供了答案。然而,在看到hk6279的评论后,我意识到可以为规范化数组提供多个目标。例如,考虑数组[40,31,140,​​131]。第一步是

array:         40  31   140  131
index:         -0  -1    -2   -3
               -----------------
normalized:    40  30   138  128

The target for the first two numbers is 35 (reachable with adjustments of +-5). The target for the second two numbers is 133 (also reachable with adjustments of +-5). So the answer is 5, and the adjustments to the array are

前两个数字的目标是35(可以调整+ -5到达)。后两个数字的目标是133(也可以通过+ -5调整到达)。所以答案是5,对数组的调整是

array:         40  31   140  131
adjustment:    -5  +5    -5   +5
               -----------------
sorted:        35  36   135  136

(Side note: the array [-15,1] also has two targets. The target for -15 is -15 with an adjustment of 0. The target for 0 (the normalized value of 1) is 0 with an adjustment of 0. So the answer is 0).

(旁注:数组[-15,1]也有两个目标。-15的目标是-15,调整为0. 0的目标值(标准化值1)为0,调整为0。所以答案是0)。

The more complicated (but still O(n)) answer

更复杂(但仍然是O(n))的答案

Step 1: Normalize the array by subtracting the array index from the value at that index. This step is unchanged from the original answer.

步骤1:通过从该索引处的值中减去数组索引来规范化数组。此步骤与原始答案相同。

Step 2: Define a data structure to hold information about the array entries.

步骤2:定义数据结构以保存有关数组条目的信息。

struct Section
{
   int max;           // the maximum value seen in this section of the array
   int min;           // the minimum value seen in this section of the array
   int startIndex;    // the starting index for this section of the array
   int endIndex;      // the ending index for this section of the array
}

Step 3: Scan the normalized array while creating an array of Section structs. (The sectionsArray may be as long as the normalized array.) The rules for creating the sectionsArray are

第3步:在创建Section结构数组的同时扫描规范化数组。 (sectionsArray可以与规范化数组一样长。)创建sectionsArray的规则是

initialize the first section as { normalized[0], normalized[0], 0, 0 }

for each subsequent entry in the normalized array
{
   if ( normalized[i] > currentSection.max )        // found a larger value than the current max
   {
      newSection = { normalized[i], normalized[i], i, i }   // create a new section and add it to the sectionsArray
      currentSection = newSection                           // the new section is now our current section
   }
   else if ( normalized[i] < currentSection.min )           // found a new minimum for the current section
   {
      currentSection.min = normalized[i]                    // update the min and end of the current section
      currentSection.endIndex = i;
   }
   else                                                     // normalized[i] is within the current range of values
   {  
      currentSection.endIndex = i;              // update the end of the current section
   }
}

Note that in this step, the max values in the sectionsArray are in strictly ascending order. This is important for the next step.

请注意,在此步骤中,sectionsArray中的最大值按严格升序排列。这对下一步很重要。

Step 4: Working backwards from the end of the sectionsArray, combine sections where possible. The rule for combining two sections is

步骤4:从sectionsArray的末尾向后工作,尽可能组合部分。组合两个部分的规则是

if ( sectionsArray[i].min <= sectionsArray[i-1].min )       // bigger max and smaller min allows preceding section to be absorbed into the current section  
{ 
   sectionsArray[i-1].max = sectionsArray[i].max            
   sectionsArray[i-1].min = sectionsArray[i].min            
   sectionsArray[i-1].endIndex = sectionsArray[i].endIndex

   discard sectionsArray[i]
}

Step 5: Scan the sectionsArray to find the largest difference between max and min. The largest difference, divided by two and rounded up if necessary, is the answer to the question. Also, the midpoint between min and max is the target value for that section of the array (target values can be truncated).

步骤5:扫描sectionsArray以找到max和min之间的最大差异。最大的差异除以2并在必要时进行四舍五入是问题的答案。此外,min和max之间的中点是数组该部分的目标值(目标值可以被截断)。

An example

Consider the array [8,5,8,6,14,12,18,13]. First normalize the array:

考虑数组[8,5,8,6,14,12,18,13]。首先规范化数组:

Input array:    8   5   8   6  14  12  18  13
index:         -0  -1  -2  -3  -4  -5  -6  -7
               ------------------------------
Normalized:     8   4   6   3  10   7  12   6

Then create the sections array:

然后创建sections数组:

{  8,  3,   0, 3 }   // started with 8, 4 became the min, 6 was in range, 3 replaced 4 as the min.  10 ended the section since it was higher than 8
{ 10,  7,   4, 5 }   // started with 10, 7 became the min.  12 ended the section.
{ 12,  6,   6, 7 }

Working backwards: The 10,7 section can be absorbed into the 12,6 section resulting in

向后工作:10,7部分可以被吸收到12,6部分中

{  8,  3,   0, 3 }
{ 12,  6,   4, 7 }

The maximum difference is 6, so the answer is 3.

最大差异为6,所以答案是3。

The target for the first section is (8+3)/2 = 5 (after truncation) The target for the second section is (12+6)/2 = 9

第一部分的目标是(8 + 3)/ 2 = 5(截断后)第二部分的目标是(12 + 6)/ 2 = 9

The adjustments are:

调整是:

Normalized:     8   4   6   3   10   7  12   6
Adjustments:   -3   1  -1   2   -1   2  -3   3
               -------------------------------
Targets:        5   5   5   5    9   9   9   9

Apply those same adjustments to the input array:

将相同的调整应用于输入数组:

Input array:    8   5   8   6   14  12  18  13
Adjustments:   -3   1  -1   2   -1   2  -3   3
               -------------------------------
Sorted:         5   6   7   8   13  14  15  16

Applying this technique to other arrays seen in this thread

将此技术应用于此线程中的其他数组

input:         4   0  9  -2
normalized:    4  -1  7  -5
sections:      { 4, -1, 0, 1 }  { 7, -5, 2, 3 }
combined:      { 7, -5, 0, 3 }
answer:        (7 - (-5)) / 2 = 6
targets:       one target for the entire normalized array => (7 + (-5)) / 2 = 1

input:         0  1  3  -15
normalized:    0  0  1  -18
sections:      { 0, 0, 0, 1 }  { 1, -18, 2, 3 }
combined:      { 1, -18, 0, 3 }
answer:        (1 - (-18)) / 2 = 10
targets:       one target for the entire normalized array => (1 + (-18)) / 2 = -8

input:         -15 1
normalized:    -15 0
sections:      { -15, -15, 0, 0 }  { 0, 0, 1, 1 }
combined:      same as above
answer:        0 (same answer for both sections)
targets:       targets are -15 and 0

input:         40  31  140  131
normalized:    40  30  138  128
sections:      { 40, 30, 0, 1 }  { 138, 128, 2, 3 }
combined:      same as above
answer:        5 (same answer for both sections)
targets:       targets are 35 and 133

The challenge

Find a counter example that breaks this algorithm and post it in the comments :)

找到一个打破这个算法的计数器示例并将其发布在评论中:)

#3

You can solve this using a binary search.

您可以使用二进制搜索来解决此问题。

• So assume that the size of the buffer is x = (low + high)/2, what you could do is from each index from 0 to n - 1 (with n is the number elements), you just need to calculate what is the minimum value it can take using buffer x (with condition that it should be greater than the last element). This greedy will help you to verify find if x can be a valid solution.

  所以假设缓冲区的大小是x =(低+高)/ 2,你可以做的是从每个索引从0到n - 1(n是数字元素),你只需要计算什么是使用缓冲区x可以采取的最小值(条件是它应该大于最后一个元素)。这种贪婪将帮助您验证查找x是否可以是有效的解决方案。

• Example , if x = 6, array is [4,0,9,-2]

  例如,如果x = 6,则数组为[4,0,9,-2]

  index 0, min is 4 - 6 = -2
  index 1, min is 0 - 1 = -1 (as we need to make this greater than -2)
  index 2, min is 9 - 6 = 3
  index 3, min is -2 + 6 = 4
  

  So, 6 is valid.

  所以,6是​​有效的。

Pseudo - code:

伪代码:

 int low = 0;
 int high = //n times Max absolute value in the array
 while(low <- high){
   int x = (low + high)/2
   if(x make the array become sorted)
      update min result;  
      high = x - 1;
   else
      low = x + 1;
 } 

#4

Here is an O(N) solution.

这是一个O(N)解决方案。

For a neighboring pair, say a and b, we need to adjust them if a > b happens. To adjust them into ascending order, we need to find an X such that a - X < b + X, which is equivalent to find X that satisfies a - b < 2X. Therefore we only need to scan the array once to find those pairs with a > b, and calculate ceil((a - b) / 2), and answer the max.

对于相邻的一对,比如说a和b,如果> b发生,我们需要调整它们。为了将它们调整为升序,我们需要找到一个X,使得a - X b的那些对,并计算ceil((a-b)/ 2),并回答最大值。

An implementation that works can be written as below:

有效的实现可以写成如下:

temp = a[0];
ans = 0
for (i = 1; i < N; i ++)
    temp = max(temp + 1, a[i])
    ans = max(ans, temp - a[i]);
return ceil(ans / 2)