将整数数组转换成之字形！
让我们再详细阐述一下这个问题。基本上，给我们一个整数数组，我们需要按照这样的顺序排列这个数组:第 1 个元素小于第 2 个元素，第 2 个元素大于第 3 个元素，第 3 个元素小于第 4 个元素，第 4 个元素大于第 5 个元素，以此类推。简而言之，输出之字形阵列中的元素顺序为[第 1 个< 2nd >第 3 个< 4th >第 5 个< 6th >第 7 个]。因此，如果给定的输入数组是[4，3，7，8，6，2，1]，之字形数组中的一个排列将是[3，7，4，8，2，6，1]。
在我们开始思考如何有效地解决它之前，这里有几点值得一提。首先，让我们假设输入数组中的所有元素都是唯一的，即整数不会重复。稍后我们还可以包含重复的整数，并扩展问题/解决方案。起初，寻找之字形数组问题看起来类似于排序，但需要注意的是，它不是严格的排序。这意味着这个问题可以有多个输出，即对于同一个输入阵列，可以找到多个之字形阵列，即一个以上的解决方案。另一点需要注意的是，之字形阵列可以是[第 1 >第 2< 3rd >第 4< 5th >第 6th】第 2 < 6 >第 4 < 8 > 7}。由于排序的时间复杂度是 O(nlogn)，这种转换成之字形的方法导致 O(nlogn)。让我们看看我们是否可以在这里改进，即是否真的需要第一次排序。
如果我们想得多一点，我们会注意到单独成对交换元素会导致之字形数组。我们实际上只需要遍历数组一次。遍历数组时，如果元素还没有按要求的顺序排列，我们可以通过交换元素来设置要求的顺序(即< or >)。为了在程序中实现这一点，让我们维护一个标志来表示需要哪个顺序(即< or >)。如果当前的两个元素不是按这个顺序排列的，那么交换这些元素，否则就不是。让我们深入研究一下这是如何工作的。假设我们当前正在处理 B 和 C，并且当前关系是输入[A B C]中的'C–因为当前关系是''。所以，关系是 A > B and B > C。我们可以推导出 A > C。所以如果我们交换 B 和 C，那么关系是 A > C 和 C < B. Finally we got the desired order i.e. [A < C > B。由于我们只遍历一次数组，时间复杂度为 0(n)
C++实现参见本。
本文由湿婆·克里希纳·阿莱提供稿。如果你发现任何不正确的地方，或者你想分享更多关于上面讨论的话题的信息，请写评论。
版权属于：月萌API www.moonapi.com，转载请注明出处
