首页 > 试题广场 >

序列交换

[编程题]序列交换
  • 热度指数:1873 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小易给你一个包含n个数字的数组。你可以对这个数组执行任意次以下交换操作:
对于数组中的两个下标i,j(1<=i,j<=n),如果为奇数,就可以交换a_ia_j

现在允许你使用操作次数不限,小易希望你能求出在所有能通过若干次操作可以得到的数组中,字典序最小的一个是什么。

输入描述:
第一行一个整数n;
第二行n个整数a_1,a_2,..,a_n,表示数组,每两个数字之间用一个空格分隔。
输入保证


输出描述:
n个整数,每两个整数之间用一个空格分隔,表示得到的字典序最小的数组。
示例1

输入

4
7 3 5 1

输出

7 3 5 1
示例2

输入

10
53941 38641 31525 75864 29026 12199 83522 58200 64784 80987

输出

12199 29026 31525 38641 53941 58200 64784 75864 80987 83522
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = scanner.nextLong();
            }
            demo1(arr);
            return;
        }
    }

    public static void demo1(long[] arr) {
        //奇数数量
        int oddSum = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] % 2 == 1) {
                oddSum++;
            }
        }
        //如果全是偶数或者全是奇数则无法排序,直接输出
        if (oddSum == 0 || oddSum == arr.length) {
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            return;
        }
        //如果至少存在一对奇偶数,则可以将序列全部从小到大排列
        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

发表于 2020-04-05 22:06:52 回复(1)
(1)如果数组中全都是奇数或者偶数,则任意两数之和一定为偶数,肯定不会执行交换操作,因此直接输出原数组。
(2)而如果数组中既有奇数也有偶数,则对数组升序排列后输出即可。下面简单说明一下我们一定可以通过若干次交换得到排序后的状态:
假如只有一个奇数,其他都是偶数,则可以用这个奇数和它排序后应该在的位置上的偶数交换。此时,任意其他位置的偶数都可以以它为中介到达正确的位置上,比如此时a5为奇数在正确的位置上,a3应该在a7的位置,则a3可以和a5先交换位置,然后a5再和a7交换位置,最后a3和a5再交换位置,这样a3就到了正确的位置上,而a5仍然在正确的位置上没有动(和两数交换的原理类似)。
如果有两个奇数,则把其中一个奇数放到正确位置上后再考虑另外一个,递归这个过程可以得到n-1个奇数也可以达到这个状态。
n = int(input())
arr = list(map(int, input().strip().split(' ')))
allOdd, allEven = 0, 0
for a in arr:
    if a % 2 == 1:
        allOdd += 1
    elif a % 2 == 0:
        allEven += 1
if (allOdd == n)&nbs***bsp;(allEven == n):    # 如果数组中全是奇数或全是偶数,则无法执行交换操作,直接输出数组
    arr = [str(i) for i in arr]
    print(' '.join(arr).strip())
else:      # 否则就是把数组排序好的状态
    arr = sorted(arr)
    arr = [str(i) for i in arr]
    print(' '.join(arr).strip())


编辑于 2020-10-22 10:59:16 回复(0)
def solve(nums):
    if len(nums) == 0:
        return []
    odd = 0
    for i in range(len(nums)):
        if nums[i] % 2 == 0:
            odd += 1
    if odd == 0&nbs***bsp;odd == len(nums):
        return nums
    else: return sorted(nums)

n = int(input())
nums = list(map(int,input().split()))
res = solve(nums)
for i in range(n):
    print(res[i],end = ' ')

发表于 2020-04-10 20:48:53 回复(4)
importjava.util.*;
publicclassMain {
    /**
     * 存在 2个奇数,2个偶数,就是排序了()
     */
    publicstaticvoidmain(String[] args) {
        Scanner scanner = newScanner(System.in);
        String line = scanner.nextLine();
        intnums = Integer.parseInt(line);
        line = scanner.nextLine();
        String[] strs = line.split(" ");
        int[] arr = newint[strs.length];
        for(inti = 0; i < strs.length; i++) {
            arr[i] = Integer.valueOf(strs[i]);
        }
        intsumOfodd = 0;
        intsumOfeven = 0;
        for(inti = 0; i < arr.length; i++) {
            if(arr[i] % 2== 0) {
                sumOfodd++;
            } else{
                sumOfeven++;
            }
        }
        //2个偶 1个奇数 或者 2个奇数 1个偶数
        if(sumOfodd >= 2&& sumOfeven >= 1|| sumOfodd >= 1&& sumOfeven >= 2|| sumOfodd == 1&& sumOfeven == 1) {
            Arrays.sort(arr);
        } else{
 
        }
        for(
                inti = 0;
                i < arr.length; i++) {
            System.out.print(arr[i]);
            if(i != arr.length - 1) {
                System.out.print(" ");
            }
        }
 
    }
 
    publicstaticvoidswap(int[] arr, inti, intj) {
        inttmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
发表于 2020-02-17 17:56:28 回复(3)
只要不全是奇数或者全是偶数,就进行排序
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n;
    cin>>n;
    long int a[n];
    int odd_num = 0;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++){
        if(a[i]&1) odd_num += 1;
    }
    if(odd_num==0 || odd_num==n){
        for(int i=0;i<n-1;i++) cout<<a[i]<<" ";
        cout<<a[n-1]<<endl;
    }
    else{
        sort(a,a+n);
        for(int i=0;i<n-1;i++) cout<<a[i]<<" ";
        cout<<a[n-1]<<endl;
    }
    
}


编辑于 2020-03-13 09:50:08 回复(0)
var n = parseInt(readline())
var arr = readline().split(" ")
var ji = arr.every(item=>Number(item)%2) //判断是否全是奇数
var ou = arr.every(item=>Number(item)%2===0) //判断是否全是偶数
if(ji||ou){
    console.log(arr.join(" "))
}else{
    arr.sort((a,b)=>a-b)
    console.log(arr.join(" "))
}
怎么简洁怎么来
发表于 2021-08-28 14:16:50 回复(0)
go实现
package main
import(
      "fmt"
      "sort")

func solve(nums []int) []int{
    if len(nums)==0 {return nums }
    odd:=0
    for _,v:= range nums{
        if v%2==0{odd++}
    }
    if odd==len(nums) || odd==0{
        return nums
    }else{
        sort.Ints(nums)
        return nums }
}
func main(){
    count:=0
    fmt.Scan(&count)
    slice:=make([]int,0)
    for i:=0;i<count;i++{
        elem:=0
        fmt.Scan(&elem)
        slice=append(slice,elem)
    }
    
    res:=solve(slice)
    for _,v:=range res{
        fmt.Printf("%d ",v)
    }
}


发表于 2022-08-19 21:45:03 回复(0)
Analysis:
如果全部是奇数或者全部是偶数,就无法进行移动;所以直接进行输出,否则对数组进行排序。因为只有里面有一个不同的,都可以通过这个唯一不同的随意移动任何数到任意位置。
implemention:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main()
{
    int n;
    cin>>n;
    vector<long long> input;
    long long temp;
    for(int i  = 0;i < n;i++)
    {
        cin>>temp;
        input.push_back(temp);
    }
    bool odd_flag = true,oven_flag = true;
    for(int i =0;i < n&&(odd_flag||oven_flag);i++)
    {
        if(input[i]%2 == 0)
        {
            odd_flag = false;
        }
        else
        {
            oven_flag = false;
       }
    }
    if(odd_flag== false&&oven_flag==false)
    {
        sort(input.begin(),input.end());
    }
    vector<long long>::iterator it;
    for(it=input.begin();it!=input.end();it++)
    {
        cout<<*it<<" ";
    }
}
测试结果:
您的代码已保存
答案正确:恭喜!您提交的程序通过了所有的测试用例

发表于 2020-08-23 19:42:01 回复(0)
全是奇数:返回原数组
全是偶数:返回原数组
否则:排序后输出
def sort_f(alist):
    odd ,even = 0,0
    for i in alist:
        if i%2 == 0:
            odd+=1
        else:
            even+=1
        if odd != 0 and even != 0:# 有奇数有偶数,直接排序
            return sorted(alist)
    return alist

n = int(input())
b = list(map(int,input().split()))
for i in sort_f(b):
    print(i,end=' ')


编辑于 2020-08-15 15:42:23 回复(0)
n = int(input())
data = [int(a) for a in input().split()]
for i in range(0,n):
    if data[i]%2 == 0:
        for j in range(i+1,n):
            if data[j]%2 != 0:
                data.sort()
    else:
        for j in range(i+1,n):
            if data[j]%2 == 0:
                data.sort()
    print(data[i],end=" ")

发表于 2020-08-08 11:00:10 回复(0)
题目我都有点理解不了,唉
发表于 2020-08-08 10:01:17 回复(0)
a = input()
b = list(map(lambda x:int(x),input().split()))
c = list(map(lambda x:x%2,b))
if sum(c) != len(c) and sum(c):
    b.sort()
print(' '.join(list(map(lambda x:str(x),b))))


好神奇
发表于 2020-08-08 09:55:58 回复(0)
python版,找出奇偶数排序即可
n = int(input())
data = list(map(int, input().split()))
odd, even = False, False
for i in data:
    if i & 1:
        odd = True
    else:
        even = True
if not odd&nbs***bsp;not even:
    print(" ".join(str(i) for i in data))
else:
    print(" ".join(str(i) for i in sorted(data)))


发表于 2020-08-08 09:46:57 回复(0)

/*
 * 如果数组元素全为奇数或者全为偶数,则不用排序,否则,排序;
 */
import java.util.Arrays;
import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        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();
        }
        jiaohuan(arr);
        // 输出
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        // System.out.println(Arrays.toString(arr));
    }

    public static void jiaohuan(int[] arr) {
        // 遍历数组,检查是否全为偶数或偶数
        // 记录奇数的个数
        int count = 0;
        ;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] % 2 == 1) { // 如果有奇数,则记录数目++
                count++;
            }
        }

        // 如果全为奇数或全为偶数,则不用排序,否则排序
        if (!(count == arr.length || count == 0)) {
            Arrays.sort(arr);
        }
    }
}

发表于 2020-08-07 20:30:32 回复(0)
是的,只要有一个数字能动,总可以把数组排成有序。
发表于 2020-08-07 10:55:20 回复(3)
def sort_f(alist):
    odd = 0  even = 0  for i in alist: if i % 2 == 0:
            odd += 1  else:
            even += 1  if odd != 0 and even != 0: # 有奇数有偶数,直接排序  return sorted(alist) return alist   a = [10,20,30,4,6,8,66,78,90] print(sort_f(a))
发表于 2020-04-05 18:44:59 回复(0)
const n = readline();
const line = readline();
let lines = line.split(' ');
for (let i = 0; i < n; i++) {
    lines[i] = parseInt(lines[i]);
};
const odd = lines.some(item => (
    (item % 2) == 1
));
const even = lines.some(item => (
    (item % 2) == 0
))
 
if (odd && even) {
    lines.sort((a, b) => (a - b));
}
 
let newlines = lines.join(' ');
console.log(newlines);

发表于 2020-02-14 22:00:02 回复(0)