首页 > 试题广场 >

完美洗牌问题（1）

[编程题]完美洗牌问题（1）

热度指数：1082 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为偶数的数组arr，长度记为2*N。前n个为左部分，后n个为右部分。arr可以表示为 $\{L_1,L_2...L_{n-1},L_n,R_1,R_2...R_{n-1},R_n \}$ ,请将数组调整成 $\{ R_1,L_1,R_2,L_2,...R_n,L_n \}$ 。

输入描述:

输入有包含两行，第一行包含一个整数n，代表arr长度。第二行包含n个整数，代表数组arr。

输出描述:

输出一行n个整数，代表调整后的数组arr。

示例1

输入

6
1 2 3 4 5 6

输出

4 1 5 2 6 3

备注:

时间复杂度，额外空间复杂度。

算法知识视频讲解

helloxuanbao

#include <stdio.h>
#include <stdlib.h>

int modifyIndex(int i, int len);

void reverse(int *arr, int l, int r);

void rotate(int *arr, int l, int m, int r);

void shuffle(int *arr, int l, int r);

void cycles(int *arr, int l, int len, int k);

int main(void) {
    int n, *arr;
    scanf("%d", &n);
    arr = (int *) malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }
    shuffle(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        if (i != 0) printf(" ");
        printf("%d", arr[i]);
    }
    printf("\n");
    free(arr);
    return 0;
}

int modifyIndex(int i, int len) {
    return (i * 2) % (len + 1);
}

void reverse(int *arr, int l, int r) {
    int t;
    while (l < r) {
        t = arr[l];
        arr[l++] = arr[r];
        arr[r--] = t;
    }
}

void rotate(int *arr, int l, int m, int r) {
    reverse(arr, l, m);
    reverse(arr, m + 1, r);
    reverse(arr, l, r);
}

void shuffle(int *arr, int l, int r) {
    int len, base, k, n, mid;
    while (r - l + 1 > 0) {
        len = r - l + 1;
        base = 1;
        k = 0;
        // 得出不超过len且满足3^k-1的最长长度
        while (base * 3 <= len + 1) {
            base *= 3;
            k++;
        }
        n = (base - 1) >> 1;
        mid = l + ((r - l) >> 1);
        rotate(arr, l + n, mid, mid + n);
        cycles(arr, l, base - 1, k);
        l += base - 1;
    }
}

void cycles(int *arr, int l, int len, int k) {
    int pre, cur, tmp;
    for (int i = 0, s = 1; i < k; i++, s *= 3) {
        pre = arr[l + s - 1];
        cur = modifyIndex(s, len);
        while (cur != s) {
            tmp = arr[l + cur - 1];
            arr[l + cur - 1] = pre;
            pre = tmp;
            cur = modifyIndex(cur, len);
        }
        arr[l + cur - 1] = pre;
    }
}

发表于 2022-02-08 15:33:56 回复(0)

F-L

#include <iostream>

using namespace std;

int arr[100001];

int get_replace_index(int index, int n)
{
    if (index < n/2)
    {
        return 2*index + 1;
    }
    return 2*index - n;
}

int main()
{
	int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
    int replace_index = 0;
    for (int i = 0; i < n; ++i)
    {
        if (arr[i] < 0)
        {
            arr[i] = -arr[i];
            continue;
        }

        replace_index = get_replace_index(i, n);
        while(replace_index != i)
        {   
            int tmp = arr[replace_index];
            arr[replace_index] = -arr[i];
            arr[i] = tmp;
            replace_index = get_replace_index(replace_index, n);
        }
    }

    for (int i = 0; i < n; ++i)
    {
        if (i > 0)
        {
            cout << " ";
        }
        cout << arr[i];
    }
    cout << endl;

	return 0;

}

发表于 2021-09-09 01:02:23 回复(0)

pein531

先读取整个序列，然后直接按洗牌后的顺序打印就行，右边的牌索引号为 n/2 + i，左边的牌索引号为 i

其中0 <= i < n/2

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strCards = br.readLine().split(" ");
        for(int i = 0; i < n / 2; i++)
            System.out.print(strCards[n/2 + i] + " " + strCards[i] + " ");
    }
}

编辑于 2021-06-23 18:00:11 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    int a[n];
    for(int i=0;i<n;i++)
        scanf("%d", &a[i]);
    for(int i=0;i<(n>>1);i++)
        printf("%d %d ", a[i+(n>>1)], a[i]);
    return 0;
}

发表于 2020-05-03 00:28:30 回复(0)

无心2019

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int>num(n);
    for(int i=0;i<n;i++)
        cin>>num[i];
    for(int i=0;i<n/2;i++)
        cout<<num[n/2+i]<<" "<<num[i]<<" ";
    return 0;  
}

发表于 2019-09-20 17:34:16 回复(0)

牛客114912041号

nums,li=int(input()),input().split()

b=zip(li[0:(len(li)//2)],li[len(li)//2:(len(li))])

for i in b:

print(*i[::-1],end=" ")

发表于 2022-11-20 17:02:43 回复(0)

牛客279399408号

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.io.IOException;

public class Main {

public static void main(String[] args) throws IOException {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int[] arr = new int[n];

for(int i=0;i<n;i++){

arr[i] = scanner.nextInt(); }

for(int i = 0; i < n / 2; i++)

System.out.print(arr[n/2 + i] + " " + arr[i] + " ");

}

发表于 2021-12-07 22:05:51 回复(0)

牛客79631828号

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        shuffle(arr);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i] + " ");
        }
        System.out.println(sb.toString().trim());
    }
    
    //获得的新位置在数组中第几位
    public static int getNewIndex(int i, int len) {
        if (i <= len / 2)
            return 2 * i;
        else 
            return 2 * (i - len/2) - 1;
    }
    
    public static void reverse(int[] arr, int L, int R) {
        while (L < R) {
            int tmp = arr[L];
            arr[L++] = arr[R];
            arr[R--] = tmp;
        }
    }
    
    public static void reversePart(int[] arr, int L, int M, int R) {
        reverse(arr, L, M);
        reverse(arr, M+1, R);
        reverse(arr, L, R);
    }
    
    /*
    下标连推，即多米诺骨牌效应，从某一位开始，使其顶掉新位置上的数，再让被顶掉
    的数去顶它的新位置上的数
    若数组长度为2*N == 3^k - 1, 则共有k个多米诺骨牌效应,且出发位置为1，3，9...3^(k-1)
    */
    public static void cycles(int[] arr, int start, int len, int k) {
        for(int i = 0, trigger = 1; i < k; i++, trigger *= 3) {
            int preVal = arr[start + trigger - 1];
            int cur = getNewIndex(trigger, len);
            while (cur != trigger) {
                int tmp = arr[start + cur - 1];
                arr[start + cur - 1] = preVal;
                preVal = tmp;
                cur = getNewIndex(cur, len);
            }
            arr[start + cur - 1] = preVal;
        }
    }
    
    public static void shuffle (int[] arr) {
        if(arr != null || arr.length != 0 || (arr.length & 1) == 0)
            shuffle2(arr, 0, arr.length-1);
    }
    
    /*
    在arr[L...R]上做洗牌，整体策略为：
    假设共2*6=12个数，先在 L1, L2, ..., R3, R4 这8个数上做下标连推，
    然后分别在L5, R5；L6, R6 这两组数上做下标连推，目的是为了使每次做下标连推
    的子数组数量都满足3^k-1. 为了实现下标连推，则必须在之前实现翻转字符串
    比方说在第一次下标连推前，把L5, L6,..., R3, R4左部分设为L5, L6, 有部分设为
    R1..R4, 然后进行翻转
    */
    public static void shuffle2(int[] arr, int L, int R) {
        while(R - L + 1 > 0) {
            int len = R-L+1;
            int base = 3;
            int k = 1;
            //计算<=len且距离len最近的，满足(3^k-1)的数
            //也就是找到最大的k，满足3^k <= len+1
            while(base <= (len+1) / 3) {
                base *= 3;
                k++;
            }
            //当前要解决base-1块，一半就是再除以2
            int half = (base-1) / 2;
            //[L...R]的中点位置
            int mid = (L+R) / 2;
            //要旋转的左部分为[L+half...mid], 右部分为arr[mid+1...mid+half]
            //注意，这里arr下标是从0开始
            reversePart(arr, L + half, mid, mid + half);
            //旋转完成后，从L开始算起，长度为base-1的部分进行下标连续推
            cycles(arr, L, base-1, k);
            L += base - 1;
        }
    }
}

此方法真正做到了在原数组中改出想要的结果，同时时间复杂度为O(N), 额外空间复杂度为O(1).

发表于 2021-07-30 17:15:14 回复(0)

Java

眼睛想旅行121

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=n/2;
        int[] a=new int[m];
        int[] b=new int[m];
        for(int i=0;i<m;i++){
            a[i]=sc.nextInt();
        }
        for(int i=0;i<m;i++){
            b[i]=sc.nextInt();
        }
        for(int i=0;i<m;i++){
            System.out.print(b[i]+" "+a[i]+" ");
        }
    }
}

发表于 2021-03-30 15:16:24 回复(0)

牛客317377475号

import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        scan.nextLine();
        String value = scan.nextLine();
        String[] arr = value.split(" ");
        //0 1 2 3 4 5
        //3 0 4 1 5 2
        StringBuffer sb = new StringBuffer();
        int center = n >>1;
        for(int i = center;i<n;i++) {
            int j = i -center;
            sb.append(arr[i] + " " + arr[j]+ " ");
        }
        System.out.print(sb.substring(0,sb.length()-1));
        
    }
    
}

发表于 2020-05-14 16:10:30 回复(0)

C/C++

别搁那忽悠人了


	#include <iostream>
(720)#include <string>



	using namespace std;



	int main()
{
 int n;
 cin >> n;



	 string s;
 cin >> s;



	 string t;
 int fir, sec;



	 fir = 0;
 sec = n / 2;



	 for (int i = 0; i < n / 2; i++){
  t += s[sec + i];
  t += s[fir + i];



	 }



	 cout << t << endl;
 system("pause");
 return 0;
}

为什么编译器上面通过这上面不给通过百分之0

发表于 2020-05-09 21:07:49 回复(0)