blocks|key|419891|text|一次完成一个单元的最小传输量是输入与所需数组不同的总量的一半。“几乎相等”似乎并不意味着根据你所给予的任何复杂情况。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|419892|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

The minimum amount of transfers done 1 unit at a time is half the total amount by which the input differs from the desired array. &quot;Almost equal&quot; doesn't seem to mean any complication according to what you've given.

blocks|key|406963|text|解决方案是想象目标数组是什么。这个目标数组将只取决于原始数组中值的和，以及数组的长度(这显然必须保持不变)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|406964|如果值的和是数组长度的倍数，那么在目标数组中，所有值都是相同的。但是，如果存在一个余数，则该余数表示数组值的数目，该值将比数组末尾的一些值多一个。|406965|我们实际上不需要存储目标数组。它是由商和和除以数组长度的剩余部分隐式定义的。|406966|该函数的输出是与任何数组索引的实际输入数组值和期望值的差额之和。我们应该只计算积极的差异(即从一个值中转移出来)，因为否则我们会计算两次--一次在传出的一侧，一次在传入的一侧。|406967|下面是基本JavaScript中的一个实现：|406968|​|406969|function+solve(arr)+{
++++//+Sum+all+array+values
++++let+sum+=+0;
++++for+(let+i+=+0;+i+<+arr.length;+i%2B%2B)+{
++++++++sum+%2B=+arr[i];
++++}

++++//+Get+the+integer+quotient+and+remainder
++++let+quotient+=+Math.floor(sum+/+arr.length);
++++let+remainder+=+sum+%25+arr.length;

++++//+Determine+the+target+value+until+the+remainder+is+completely+consumed:++++++++
++++let+expected+=+quotient+%2B+1;

++++//+Collect+all+the+positive+differences+with+the+expected+value
++++let+result+=+0;
++++for+(let+i+=+0;+i+<+arr.length;+i%2B%2B)+{
+++++++//+If+we+have+consumed+the+remainder,+reduce+the+expected+value
+++++++if+(i+==+remainder)+{
+++++++++++expected+=+quotient;
+++++++}
+++++++let+transfer+=+arr[i]+-+expected;
+++++++//+Only+account+for+positive+transfers+to+avoid+double+counting
+++++++if+(transfer+>+0)+{
+++++++++++result+%2B=+transfer;
+++++++}
++++}
++++
++++return+result;
}

let+array+=+[7,2,2];
console.log(solve(array));+//+6|code-block|syntax|javascript|406970|406971|entityMap^0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|T|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|U|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|V|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|W|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|X|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|Y|8|@]|9|@]|A|$]]|$1|L|3|M|5|N|7|Z|8|@]|9|@]|A|$O|P]]|$1|Q|3|K|5|6|7|10|8|@]|9|@]|A|$]]|$1|R|3|-4|5|6|7|11|8|@]|9|@]|A|$]]]|S|$]]

The solution is to imagine what the target array will be. This target array will depend only on the sum of the values in the original array, and the length of the array (which obviously must remain the same).
If the sum of the values is a multiple of the array length, then in the target array all values will be the same. If however there is a remainder, that remainder represents the number of array values that will be one more than some of the value(s) at the end of the array.
We don't actually have to store that target array. It is implicitly defined by the quotient and the remainder of the division of the sum by the array length.
The output of the function is the sum of differences with the actual input array value and the expected value at any array index. We should only count positive differences (i.e. transfers out of a value) as otherwise we would count transfers twice -- once on the outgoing side and again on the incoming side.
Here is an implementation in basic JavaScript:
<div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
<div class="snippet-code">
<pre class="snippet-code-js lang-js prettyprint-override"><code>function solve(arr) {
 // Sum all array values
 let sum = 0;
 for (let i = 0; i &lt; arr.length; i++) {
 sum += arr[i];
 }

 // Get the integer quotient and remainder
 let quotient = Math.floor(sum / arr.length);
 let remainder = sum % arr.length;

 // Determine the target value until the remainder is completely consumed: 
 let expected = quotient + 1;

 // Collect all the positive differences with the expected value
 let result = 0;
 for (let i = 0; i &lt; arr.length; i++) {
 // If we have consumed the remainder, reduce the expected value
 if (i == remainder) {
 expected = quotient;
 }
 let transfer = arr[i] - expected;
 // Only account for positive transfers to avoid double counting
 if (transfer &gt; 0) {
 result += transfer;
 }
 }
 
 return result;
}

let array = [7,2,2];
console.log(solve(array)); // 6</code></pre>
</div>
</div>

blocks|key|419965|text|让我们从目标数组开始。那是什么？|type|unstyled|depth|inlineStyleRanges|entityRanges|data|419966|有了{7,+2,+2}，我们就想得到{4,+4,+3}。因此，每个项目至少是3，一些顶级项目是3+%2B+1+==+4。算法是|offset|length|style|CODE|419967|let+sum+=+sum(original)
let+rem+=+sum(original)+%25+length(original)++#+here+%25+stands+for+remainder

target[i]+=+sum+/+length(original)+%2B+(i+<+rem+?+1+:+0)+|code-block|syntax|javascript|419968|有original和target|419969|original:+7+2+2
target:+++4+4+3
transfer:+3+2+1+(6+in+total)|419970|注意，那|419971|transfer[i]只是一个绝对的区别：abs(original[i]+-+target[i])|ordered-list-item|419972|我们对每个transfer进行两次计数:一次减去，然后再加。|419973|所以答案是|419974|sum(transfer[i])+/+2+==+sum(abs(original[i]+-+target[i]))+/+2+|419975|码(c#)|BOLD|419976|private+static+int+Solve(int[]+initial)+{
++//+Don't+forget+about+degenerated+cases
++if+(initial+is+null+%7C%7C+initial.Length+<=+0)
++++return+0;++

++int+sum+=+initial.Sum();
++int+rem+=+sum+%25+initial.Length;

++int+result+=+0;

++for+(int+i+=+0;+i+<+initial.Length;+%2B%2Bi)+
++++result+%2B=+Math.Abs(sum+/+initial.Length+%2B+((i+<+rem)+?+1+:+0)+-+initial[i]);
++
++return+result+/+2;++
}|419977|演示：+(小提琴)|419978|++++int[][]+tests+=+new+int[][]+{
++++++++new+int[]+{7,+2,+2},
++++++++new+int[]+{2,+2,+7},
++++++++new+int[]+{},
++++++++new+int[]+{2,+2,+2},
++++++++new+int[]+{1,+2,+3},
++++};
++++
++++string+report+=+string.Join(Environment.NewLine,+tests
++++++.Select(test+=>+$"[{string.Join(",+",+test)}]+=>+{Solve(test)}"));
++++
++++Console.Write(report);|419979|结果：|419980|[7,+2,+2]+=>+3
[2,+2,+7]+=>+4
[]+=>+0
[2,+2,+2]+=>+0
[1,+2,+3]+=>+1|419981|entityMap|0|LINK|mutability|MUTABLE|url|https://dotnetfiddle.net/se8fKN^0|0|2|9|I|9|12|1|1B|A|0|0|1|8|A|6|0|0|0|0|B|L|S|0|5|8|0|0|0|0|5|0|0|0|3|5|3|0|0|0|0|3|0|0^^$0|@$1|2|3|4|5|6|7|1M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1N|8|@$D|1O|E|1P|F|G]|$D|1Q|E|1R|F|G]|$D|1S|E|1T|F|G]|$D|1U|E|1V|F|G]]|9|@]|A|$]]|$1|H|3|I|5|J|7|1W|8|@]|9|@]|A|$K|L]]|$1|M|3|N|5|6|7|1X|8|@$D|1Y|E|1Z|F|G]|$D|20|E|21|F|G]]|9|@]|A|$]]|$1|O|3|P|5|J|7|22|8|@]|9|@]|A|$K|L]]|$1|Q|3|R|5|6|7|23|8|@]|9|@]|A|$]]|$1|S|3|T|5|U|7|24|8|@$D|25|E|26|F|G]|$D|27|E|28|F|G]]|9|@]|A|$]]|$1|V|3|W|5|U|7|29|8|@$D|2A|E|2B|F|G]]|9|@]|A|$]]|$1|X|3|Y|5|6|7|2C|8|@]|9|@]|A|$]]|$1|Z|3|10|5|J|7|2D|8|@]|9|@]|A|$K|L]]|$1|11|3|12|5|6|7|2E|8|@$D|2F|E|2G|F|13]]|9|@]|A|$]]|$1|14|3|15|5|J|7|2H|8|@]|9|@]|A|$K|L]]|$1|16|3|17|5|6|7|2I|8|@$D|2J|E|2K|F|13]]|9|@$D|2L|E|2M|1|2N]]|A|$]]|$1|18|3|19|5|J|7|2O|8|@]|9|@]|A|$K|L]]|$1|1A|3|1B|5|6|7|2P|8|@$D|2Q|E|2R|F|13]]|9|@]|A|$]]|$1|1C|3|1D|5|J|7|2S|8|@]|9|@]|A|$K|L]]|$1|1E|3|-4|5|6|7|2T|8|@]|9|@]|A|$]]]|1F|$1G|$5|1H|1I|1J|A|$1K|1L]]]]

Let's start form target array. What is it?
Having <code>{7, 2, 2}</code> we want to obtain <code>{4, 4, 3}</code>. So every item is at least <code>3</code> and some top items are <code>3 + 1 == 4</code>.
The algorithm is
<pre><code>let sum = sum(original)
let rem = sum(original) % length(original) # here % stands for remainder

target[i] = sum / length(original) + (i &lt; rem ? 1 : 0) 
</code></pre>
Having <code>original</code> and <code>target</code>
<pre><code>original: 7 2 2
target: 4 4 3
transfer: 3 2 1 (6 in total)
</code></pre>
note, that
<ol>
<li><code>transfer[i]</code> is just an absolute difference: <code>abs(original[i] - target[i])</code></li>
<li>we count each <code>transfer</code> twice: once we subtract and then we add.</li>
</ol>
So the answer is
<pre><code>sum(transfer[i]) / 2 == sum(abs(original[i] - target[i])) / 2 
</code></pre>
Code (c#):
<pre><code>private static int Solve(int[] initial) {
 // Don't forget about degenerated cases
 if (initial is null || initial.Length &lt;= 0)
 return 0; 

 int sum = initial.Sum();
 int rem = sum % initial.Length;

 int result = 0;

 for (int i = 0; i &lt; initial.Length; ++i) 
 result += Math.Abs(sum / initial.Length + ((i &lt; rem) ? 1 : 0) - initial[i]);
 
 return result / 2; 
}
</code></pre>
Demo: (<a href="https://dotnetfiddle.net/se8fKN" rel="nofollow noreferrer">Fiddle</a>)
<pre><code> int[][] tests = new int[][] {
 new int[] {7, 2, 2},
 new int[] {2, 2, 7},
 new int[] {},
 new int[] {2, 2, 2},
 new int[] {1, 2, 3},
 };
 
 string report = string.Join(Environment.NewLine, tests
 .Select(test =&gt; $&quot;[{string.Join(&quot;, &quot;, test)}] =&gt; {Solve(test)}&quot;));
 
 Console.Write(report);
</code></pre>
Outcome:
<pre><code>[7, 2, 2] =&gt; 3
[2, 2, 7] =&gt; 4
[] =&gt; 0
[2, 2, 2] =&gt; 0
[1, 2, 3] =&gt; 1
</code></pre>

blocks|key|407010|text|在我看来，这是一个可以用greedy方法解决的简单问题。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|407011|步骤：|407012|总结input数组-元素S，除以其长度n.比方说，商数是Q，余数(mod)是R。然后，最终数组target将有1st+R+elements+with+value+=+Q%2B1。其余的元素将是Q。|ordered-list-item|407013|传输的数量将是input+and+target数组中每个(对应)位置绝对差之和的一半。|407014|示例：|407015|Input+[7,+2,+2]
S=11+n=3+Q=11/3=3+R=11%253=2
Target+[3%2B1,+3%2B1,+3]
Answer+=+(abs(7-4)+%2B+abs(2-4)+%2B+abs(2-3))+/+2+=+3|code-block|syntax|javascript|407016|entityMap^0|C|6|0|0|2|5|C|1|J|1|S|1|12|1|1B|6|1J|V|2M|1|0|7|G|0|0|0^^$0|@$1|2|3|4|5|6|7|V|8|@$9|W|A|X|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|Y|8|@]|D|@]|E|$]]|$1|H|3|I|5|J|7|Z|8|@$9|10|A|11|B|C]|$9|12|A|13|B|C]|$9|14|A|15|B|C]|$9|16|A|17|B|C]|$9|18|A|19|B|C]|$9|1A|A|1B|B|C]|$9|1C|A|1D|B|C]|$9|1E|A|1F|B|C]]|D|@]|E|$]]|$1|K|3|L|5|J|7|1G|8|@$9|1H|A|1I|B|C]]|D|@]|E|$]]|$1|M|3|N|5|6|7|1J|8|@]|D|@]|E|$]]|$1|O|3|P|5|Q|7|1K|8|@]|D|@]|E|$R|S]]|$1|T|3|-4|5|6|7|1L|8|@]|D|@]|E|$]]]|U|$]]

Seems to me like a simple problem that can be solved with <code>greedy</code> approach.
<h2>Steps:</h2>
<ol>
<li>Sum up the <code>input</code> array-elements <code>S</code>, divide by its length <code>n</code>. Lets say, the quotient is <code>Q</code> and remainder (mod) is <code>R</code>. Then, final array <code>target</code> will have <code>1st R elements with value = Q+1</code>. Rest of the elements will be <code>Q</code>.</li>
<li>Number of transfers will be half of the sum of absolute difference at each (corresponding) position in <code>input and target</code> arrays.</li>
</ol>
<h2>Example:</h2>
<pre><code>Input [7, 2, 2]
S=11 n=3 Q=11/3=3 R=11%3=2
Target [3+1, 3+1, 3]
Answer = (abs(7-4) + abs(2-4) + abs(2-3)) / 2 = 3
</code></pre>

This question is asked in the interview. I am still not able to find what should be right approach to attempt this problem.
Given an array = [7,2,2] find the minimum number of transfer required to make array elements almost equal. If this is not possible the larger elements should come to the left side.
In above example the final state of array would be [4,4,3] and the answer will be 2+ 1 =3.
We are transfering 2 from 7 to first 2 and then we are transfering another 1 from 7 to 2.
If the input is [2,2,7] then the answer will be 4 since we need to keep bigger elements on the left side.
final state = [4,4,3]
2 transfered from 7 to both 2 to make the final count as 4.

Minimum transfer to make array equal

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

这个问题是在面试中提出的。我仍然无法找到正确的方法来尝试这个问题。给定数组= 7,2,2找到使数组元素几乎相等所需的最小传输数。如果这是不可能的，更大的元素应该出现在左边。在上面的例子中，数组的最终状态是4,4,3，答案是2+ 1 =3。我们将2从7转移到前2，然后我们将另1从7转移到2。如果输入是2,2,7，那么答案...

问使数组相等的最小传输
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问使数组相等的最小传输EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问使数组相等的最小传输
EN