应用归并排序逻辑
我正在尝试解决一个问题，我将使用合并排序来获得以下情况： 在 n 个元素的数组中，
获取数组中最小的数字，然后获取最大的数字，因此它们的减法（或这些数字之间的差异最大）
例如： n = 8 到达 {7,8,10,20,4,19,50,70} 我想要 4 和 70，因为它们的差是 66 如果我得到最小和最大的数字并不重要，我只关心它们相减的最大差异。另外，第一个数字必须小于第二个数字，不允许使用 70 和 4。
因为这个问题需要我修改归并排序代码，所以我在想：1）将所有数字分为1、2）将数组中的第i个数字与第i+1个数字进行比较，如果第i个数字是最低的那么得到它们的差异并继续遍历数组中的所有位置。
你怎么认为？我在设置基本情况时也遇到问题：S请帮忙！
I'm trying to solve a problem where I am to use merge sort to get the following case:
in an array of n elements
get the lowest number on an array and then get the biggest number SO their subtraction (or difference between those numbers is biggest)
for example:
n = 8
arr {7,8,10,20,4,19,50,70}
I want to get 4 and 70, because their difference is 66
It really doesn't matter if I get the lowest and the biggest numbers, I only care for the biggest difference in their subtraction. ALSO, THE FIRST NUMBER MUST BE LOWEST THAN THE SECOND ONE, 70 and 4 is not allowed.
because this problem requires me to modify merge sort code, I was thinking: 1) get all the numbers divided into arrays of 1, 2) compare the i number in the array to the i+1 number, and if i number is lowest then get their difference and keep moving through all the positions in the array.
what do you think? also I'm having problem with setting the base case :S please help!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
合并排序的理念是将较小部分的结果合并到较大部分中。
在合并排序中，首先将 2 个元素（2 个包含 1 个元素的数组）合并为一个包含 2 个元素的排序数组，然后将 2 个包含 2 个元素的排序数组合并为一个包含 4 个元素的排序数组（因为这 2 个数组已排序，所以您只需要遍历并比较（按升序排序，较小的元素总是在两个数组中排在前面），然后将 2 个 4 个元素的排序数组合并为 8 个元素的排序数组。
现在，你只需要找到最大和最小，因此，你只需要找到2个元素中的最大和最小。比较 2 个 2 个元素的数组中的 2 个最大元素并找到较大的元素，然后比较 2 个 4 个元素的数组中的 2 个最大元素并找到较大的元素，依此类推。 （小边也一样。）
换句话说，你不再对整个数组进行排序，而是找到最大和最小并合并结果以获得最终答案。
顺便说一句，我认为这有点像快速选择快速排序。
Merge-sort's philosophy is to merge results from smaller segments into bigger ones.
In merge-sort, first you merge 2 elements (2 arrays of 1 element) into a sorted array of 2 elements, and then merge 2 sorted arrays of 2 elements into a sorted array of 4 elements (because the 2 arrays are sorted, you only need to traverse and compare, smaller elements always come first in both arrays in an ascending sort), and then merge 2 sorted arrays of 4 elements into a sorted array of 8 elements.
Now, you only need to find the largest and the smallest, thus, you only need to find the largest and smallest in 2 elements. Compare the 2 largest elements from 2 arrays of 2 elements and find the larger, and then compare the 2 largest elements from 2 arrays of 4 elements and find the larger, and so forth. (Same for the small side.)
In other words, you no longer sort the whole array, but find the largest and smallest and merge results to get the final answer.
I think it is a little bit like quick-select to quick-sort, by the way.
基本的合并排序对数组进行排序，因此您可以轻松获得最大和最小的数字。但你只是想修改数组，以便只得到最大和最小的数字——你不关心中间的数字。一旦你认出它们，它们实际上就是垃圾。
如何确定您正在查看的数字是否无用？好吧，如果它既不是当前范围内的最小数字，也不是最大数字。
首先查看合并排序的伪代码。为了更彻底地解决这个问题，您可以做出哪些最小的改变？
A basic merge sort sorts your array, so you easily get the biggest and smallest numbers. But you're just trying to modify the array so that you only get the biggest and smallest numbers -- you don't care about the ones in the middle. They're effectively garbage, once you identify them.
How can you identify if a number you're looking at is useless? Well, if it's the case that it's both not the smallest and not the biggest number in your current scope.
Start by looking at the psuedo-code for merge sort. What are the smallest changes you can make to more closely solve this problem?