我要招人

去企业版

首页 > 试题广场 >

小美的排列构造

[编程题]小美的排列构造

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

小美定义一个数组 $a$ 的权值计算如下：

首先将 $a$ 的每一对相邻两项求和，得到一个 $b$ 数组。那么 $b$ 数组的最大值减最小值即为 $a$ 数组的权值。

例如，若 $a=[2,1,3]$ ，那么 $b=[3,4]$ ， $b$ 数组的极差是1。因此 $a$ 数组的权值为1。

现在小美希望你能构造一个长度为 $n$ 的排列，满足权值尽可能小。你能帮帮她吗？

排列是指一个长度为 $n$ 的数组，其中 1 到 $n$ 每个元素恰好出现一次。

输入描述:

一个正整数，代表排列的长度。

输出描述:

一个合法的排列。如果有多解输出任意即可。

示例1

输入

输出

2 1 3

说明

这个数组的权值为 1。输出[2,3,1]等排列也是合法的。

算法知识视频讲解

Python

longkouding

import sys
 
for line in sys.stdin:
    a = line.split()
     
n = int(a[0])
res = [0 for i in range(n)]
max_n = n
min_n = 1
for i in range(1,n,2):
    res[i] = max_n
    max_n = max_n - 1
 
for i in range(0,n,2):
    res[i] = min_n
    min_n +=1
out = " ".join(str(r) for r in res)
print(out)

编辑于 2023-08-18 18:34:31 回复(0)

Python

秋招早日上岸

python,这道题的思路就是从一个1到n的数组中，重新排列，数字组间和之差最小。最理想的方案就是每次只取数组中的最大值和最小值.最终就会得到这样的一个数组[n,1, n-1,2, n-2,3, ..., n//2]，然后将数组逆序转换成字符串

def sol(n):
    arr = [i+1 for i in range(n)]
    arr.sort(reverse=True)
    ans = []
    left,right = 0,n-1
    while left<=right:
        if left == right:
            ans.append(arr[left])
            break
        ans.append(arr[left])
        ans.append(arr[right])
        left += 1
        right -=1
    str_ans = ' '.join([str(x) for x in ans[::-1]]).strip()
    return str_ans
while 1:
    try:
        n = int(input())
        ans = sol(n)
        print(ans)
    except:
        break

发表于 2023-10-21 02:40:37 回复(0)

C/C++

听说改名字就有offer

看我，看我，时间复杂度O(n),空间复杂度O(1)。

#include <iostream>
using namespace std;

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

    int left = 2;
    int right = n;
    cout << 1 << " ";
    bool flag = true;
    while(left<=right){
        if(flag){
            cout << right <<" ";
            --right;
        }
        else{
            cout << left << " ";
            ++left;
        }
        flag=!flag;
    }
    cout <<endl;
}

发表于 2024-08-12 17:04:52 回复(0)

Python

suwueng

这个只要想到了一种排列方式就行，可以将数分成前后两部分，前一部分正序排列，后一部分逆序排列，两部分交错合并，就比如：

1～8:

step1 分为两部分，1 2 3 4 和 5 6 7 8

step2 后一部分逆序，变成1 2 3 4 和 8 7 6 5

step3 交错合并， 1 8 2 7 3 6 4 5

import sys

n = int(input())

m = n // 2
ans = []
for i in range(m):
    ans.append(i+1)
    ans.append(n - i)
if n % 2:
    ans.append(m + 1)
    for i in ans:
        print(i, end=' ')
else:
    for i in ans:
        print(i, end=' ')

发表于 2024-03-09 21:16:09 回复(1)

在投简历的安哥拉兔很能干

发表于 2023-09-10 21:16:37 回复(0)

C/C++

杰超123

双指针左右分别输出即可

#include <iostream>

using namespace std;

int main() {

int n;

cin>>n;

int left = 1;

int right = n;

while(left<=right){

cout<<left<<" ";

if(left<right) cout<<right<<" ";

left++;

right--;

}

return 0;

}

发表于 2024-08-23 23:13:01 回复(0)

小尘u

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), flag = 1;
        Deque<Integer> q = new LinkedList<>();
        for (int i = 1, j = n; i <= j; i++, j--) {
            if (flag == 1) {
                q.offerFirst(i);
                if (i < j)
                    q.offerFirst(j);
 
            }
        }
        for (int a : q) {
            System.out.printf(a + " ");
        }
    }

编辑于 2024-04-11 13:51:18 回复(0)

Goree

public static void main(String[] args) { int left = 1;  int right = new Scanner(System.in).nextInt();   StringBuilder stringBuilder = new StringBuilder();   while(left < right) {
        stringBuilder.append(left).append(" ").append(right).append(" ");  left ++;  right --;  } if (left == right) {
        stringBuilder.append(left);  }
    System.out.println(stringBuilder);  }

编辑于 2024-04-03 15:10:21 回复(0)

再快点啊啊啊

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for(int i=1;i<=n/2;i++){
            System.out.print(n-i+1);
            System.out.print(" ");
            System.out.print(i);
            if(i!=n/2)System.out.print(" ");


        }
        if(n%2 == 1) {
            System.out.print(" ");
            System.out.print(n - n / 2);
        }

    }
}

发表于 2024-03-13 13:56:25 回复(0)

Java

Innocence24

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static final Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        question05();
    }

  private static void question05() {
    int left = 1, right = sc.nextInt();
    StringBuilder sb = new StringBuilder();
    while (left < right) {
      sb.append(left++).append(" ").append(right--).append(" ");
    }
    if (left == right) {
      sb.append(left);
    }
    System.out.println(sb);
  }
}

发表于 2023-09-12 18:53:10 回复(0)

C/C++

酸菜秋刀鱼

#include <iostream>
#include <vector>
using namespace std;

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

    //初始化构造顺序排列
    vector<int> a;
    int i = 1, j = n;
    // int mid = n/2 + 1;
    while(a.size()<n && i < j ){
        // 交叉重新排列数组
        a.push_back(i);
        a.push_back(j);
        i++;
        j--;
    }
    a.push_back(i);
    for(int c = 0; c<n; c++){
        cout << a[c] << " ";
    }
    }

// 64 位输出请用 printf("%lld")

发表于 2023-08-22 01:38:45 回复(0)

我嘞个逗

#include <iostream>

#include <vector>

using namespace std;

void paile(int n, vector<int>& result) {

if (n == 1) result[0] = 1;

else if (n == 2) {

result[0] = 1;

result[1] = 2;

} else if (n >= 3) {

int temp = n / 2 + 1;

int num;

result[0] = temp;

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

if (i % 2 == 0) {

num = i / 2;

result[i] = temp + num;

} else {

num = i / 2 + 1;

result[i] = temp - num;

}

int main() {

int n;

cin >> n;

vector<int> result(n, 0);

paile(n, result);

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

cout << result[i] << " ";

}

return 0;

}

发表于 2023-08-18 15:22:35 回复(0)

提交观点

问题信息

来自：美团2023年秋招笔试...

难度：

12条回答 45收藏 2101浏览

小美的排列构造

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题