交替排列阵列
给定一个排序的正整数数组。您的任务是交替地重新排列数组元素，即第一个元素应该是最大值，第二个元素应该是最小值，第三个元素应该是第二个最大值，第四个元素应该是第二个分钟，等等。
class RearrangeAlternate{
public void swapMax(int arr[], int i, int n){
int x = arr[i];
int j;
for(j = n-1; j>i; j--){
if(arr[j] > x){
break;
}
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public void swapMin(int arr[], int i, int n){
int x = arr[i];
int j;
int res = n-1;
for(j = n-1; j>i; j--){
if(arr[j] < x){
if(arr[j] < arr[res]){
res = j;
}
}
}
int temp = arr[i];
arr[i] = arr[res];
arr[res] = temp;
}
public void rearrange(int arr[], int n){
for(int i = 0; i<n; i++){
if(i%2 == 0){
swapMax(arr, i, n);
}
else swapMin(arr, i, n);
}
}
}请帮我找出错误
它显示出错误的输出对某些部分。 例如： 82 12 23 28 43 44 59 68 68 70 85 88 124 125 136 168 171 173 179 199 212 230 277 302 306 316 325 328 337 363 365 368 368 369 371 374 387 394 414 422 427 430 435 493 506 527 531 538 541 541 541 546 568 583 691 730 737 751 764 778 783 785 789 794 803 809 803 809 815 847 847 858 863 874 896 916 926 927 927 957 981 997我的代码输出: 997 12 981 23 930 43 927 44 926 920 920 916 68 896 887 85 874 892 863 858 8125 8125 815 809 803 809 803171 794 173 789 179 785 199 783 212 778 230 764 277 751 282 737 306 730 314 691 316 325 568 527 336 506 527 506 337 430 363 374 364 583 368 531 393 493 387 538 594 457 414 422 546 427答复: 997 12 981 23 957 23 930 28 930 44 926 59 920 60 916 68 896 85 874 88 863 92 858 124 874 88 863 92 858 124 847 125 815 809 168 803 171 171 173 789 179 785 199 783 212 778 767 764 277 751 302 30730 330 691 316 325 583 568 546 546 337 541 365 531 365 531 365 531527 369 506 371 493 374 457 387 435 394 430 414 427 422
回答 5
Stack Overflow用户
发布于 2020-04-14 12:15:29
由于您的数组是排序的，所以您可以这样做：
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int temp;
for (int i = 0; i < arr.length; i++) {
if (i % 2 == 0) {
// Store the last element to 'temp'
temp = arr[arr.length - 1];
// Shift all elements, starting from index, 'i', to one place right
for (int j = arr.length - 2; j >= i; j--) {
arr[j + 1] = arr[j];
}
// Put the value stored in 'temp' to index, 'i'
arr[i] = temp;
}
}
System.out.println(Arrays.toString(arr));
}
}输出：
[10, 1, 9, 2, 8, 3, 7, 4, 6, 5]Stack Overflow用户
发布于 2020-06-10 14:05:43
由于数组是排序的，我们需要重新排列，因此我们可以使用这种技术将两个数字存储在一个位置上，这样我们也可以在需要时检索原始元素。假设我们需要将n1和n2存储在同一个位置，那么我们可以将其表述为：
====================== n1 = n1 + (n2%z)*z ======================
要提取n1，我们可以用z来提取n1，而为了提取n2，我们可以将n1除以z。
Stack Overflow用户
发布于 2021-02-06 09:34:31
本文提出的解决方案解决了O(N)时间复杂度和O(1)空间复杂度中使用“在一个位置存储2个值”的问题。此外，该算法还可以处理重复的值&浮点值，因为输入列表是不减少排序的，并且只由正整数组成。
PS:如果你愿意的话，你可以稍微修改一下我的算法，让它也适用于负值。
请不要因看代码而感到害怕。实现非常简单。算法可能有点难理解。
def reArrange(arr, print_arr_state=True):
# arr: non-decreasingly sorted list of positive floats/ints
length = len(arr)
for i in range(length):
if arr[i] > 0:
cycler(arr, i, length, print_arr_state)
arr[i] = abs(arr[i]) # This is the tricky part
# printing the array after every iteration
if print_arr_state:
print('after', i, 'th iteration:', arr)
def cycler(arr, start_index, length, print_cycler_array=True):
if print_cycler_array:
print('cycler function:', arr, end=' ---> ')
half_length_index = length // 2
swap_index = start_index
current_value = arr[start_index]
while True:
if swap_index < half_length_index:
swap_index = 2 * swap_index + 1
else:
swap_index = 2 * (length - 1 - swap_index)
# Placing the current value at swap_index and making the making current_value variable refer to the value which was at swap_index
swap_value = arr[swap_index]
arr[swap_index] = -1 * current_value # -1 * ?? This is the tricky part of the algo
current_value = swap_value
# cycler function will not stop until the simple cycle is complete
# simple cycle is complete when swap_index == start_index
if swap_index == start_index:
if print_cycler_array:
print(arr)
return提供输入(input_array)和调用reArrange函数：
input_array = [0.1, 2, 3.2, 3.3, 3.3, 4, 5.7, 5.7, 6.8, 7, 8, 9]
reArrange(input_array)输出：
answer_array = [9, 0.1, 8, 2, 7, 3.2, 6.8, 3.3, 5.7, 3.3, 5.7, 4]理解算法
算法的棘手部分：
每个值都完全属于1圈，这个循环是一个简单的循环(图中的简单圈与复圈)。循环函数的一次执行对应于一个周期，这也是一个简单的循环。
每当我在循环中覆盖一个值时，我都会将其乘以-1 (以表示它已被覆盖)，并将其存储在输入数组本身中。在reArrange函数循环的第一次迭代中，如果我发现第一次值是负的，我就会得到一个指示，表明这个值是为某些j-迭代执行的循环的一部分(其中j< i)，因此我不调用这个值上的cycler函数。但是如果这个值是正的(表示到目前为止执行的循环都没有覆盖这个值)，它意味着它还没有被覆盖，因此应该在使用cycler函数的第一次迭代中覆盖。
但是等等！，如果我将所有值乘以-1，我的最终答案将是-1 * 为了解决这个问题，一种解决方案是重申我的answer_array (最初是input_array，现在已经转换为answer_array)，并取每个值或的绝对值，在第一次也是唯一一次迭代( reArrange函数的循环)中，通过在I+1迭代之前获取值的绝对值来完成相同的工作。
一些有效的问题
这个算法有几个方面我在这篇文章中没有提到。请允许我以以下形式提出以下几个方面：
- cycler函数的while循环是否保证终止？
- 为什么我们不应该覆盖一个不止一次的价值？
- 我们如何处理负输入值(如果有的话)？
- 不足以涵盖input_array的所有值。(自行车函数的一个调用不足以覆盖所有的值)？ 提示:例如:1 2 3 4 5 6 7，这个例子将导致3个周期。(cycler函数称为三次函数)
- 单次调用自行车功能会发生什么？ 提示:这个周期中的每个值都会转移到它应该在correct_answer_array中的位置。一旦一个值在其正确的位置，它就不应该再受到干扰。
请访问此页(GeeksforGeeks)底部的注释部分，查看算法的试运行。请务必阅读我的所有评论，因为我在那里制造了一点混乱。
https://stackoverflow.com/questions/61206959
复制相似问题
腾讯云开发者
