首页 > 试题广场 >

奇数下标都是奇数或者偶数下标都是偶数

[编程题]奇数下标都是奇数或者偶数下标都是偶数
  • 热度指数：1972 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个长度不小于2的数组arr，实现一个函数调整arr，要么让所有的偶数下标都是偶数，要么让所有的奇数下标都是奇数
注意：1、数组下标从0开始！
2、本题有special judge，你可以输出任意一组合法解！同时可以证明解一定存在
[要求]
时间复杂度为，额外空间复杂度为


输入描述:
第一行一个整数N。表示数组长度
接下来一行N个整数表示数组内的数


输出描述:
输出N个整数。表示调整后的数组
示例1

输入

5
1 2 3 4 5

输出

2 1 4 3 5

说明

样例中的输出保证了奇数下标都是奇数

备注:

算法知识视频讲解
添加回答
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, l=0, r=1;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    while(l<n && r<n){
        while(!(a[l]&1))
            l+=2;
        while(a[r]&1)
            r+=2;
        if(l<n && r<n)
            swap(a[l], a[r]);
    }
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    return 0;
}

发表于 2020-02-17 00:51:23 回复(0)
Java
小星教授头像 小星教授 
import java.util.*;

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();
        }
        
        int even = 0;
        int odd = 1;
        while(true){
            while(even < n){
                if(arr[even] % 2 == 0){
                    even += 2;
                }else{
                    break;
                }
            }
            while(odd < n){
                if(arr[odd] % 2 == 1){
                    odd += 2;
                }else{
                    break;
                }
            }
            if(even >= n || odd >= n) break;
            swap(arr,even,odd);
            
        }
        
       for(int i=0;i<n;i++){
            System.out.print(arr[i] + " ");
        }
		
	}
    
    public static void swap(int[] arr,int even,int odd){
        int temp = arr[even];
        arr[even] = arr[odd];
        arr[odd] = temp;
    }
}

发表于 2019-10-23 18:10:23 回复(0)
C
helloxuanbao头像 helloxuanbao 
#include <stdio.h>
#include <stdlib.h>

void swap(int *arr, int i, int j) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}

int main(void) {
    int n, *arr;
    scanf("%d", &n);
    arr = (int *) malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }
    
    int even = 0, odd = 1;
    while (even < n && odd < n) {
        if (arr[n - 1] & 1) {
            swap(arr, odd, n - 1);
            odd += 2;
        } else {
            swap(arr, even, n - 1);
            even += 2;
        }
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

发表于 2022-04-04 21:04:12 回复(0)
pein531头像 pein531
初始化一个偶数下标指针0和一个奇数下标指针1，以步长为2来移动它们。直到至少一个指针越界，表示已经完成了奇数下标都是奇数或偶数下标都是偶数。
（1）在移动的过程中如果奇数下标的元素为奇数或者偶数下标为偶数就分别移动奇数下标指针和偶数下标指针。
（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().trim());
        String[] strArr = br.readLine().trim().split(" ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(strArr[i]);
        adjust(arr);
        for(int i = 0; i < n; i++) System.out.print(arr[i] + " ");
    }
    
    private static void adjust(int[] arr) {
        int even = 0, odd = 1;
        while(even < arr.length && odd < arr.length){
            while(even < arr.length && arr[even] % 2 == 0) even += 2;
            while(odd < arr.length && arr[odd] % 2 == 1) odd += 2;
            if(even < arr.length && odd < arr.length){
                int temp = arr[even];
                arr[even] = arr[odd];
                arr[odd] = temp;
            }
        }
    }
}

发表于 2021-06-20 20:11:38 回复(0)
秃头一半头像 秃头一半 

#include<iostream>
(720)#include<algorithm>
 
using namespace std;
 
int main(){
    int n;
    cin>>n;
    int inp[n];
    for(int i = 0; i < n; i++){
        scanf("%d",&inp[i]);
    }
    int even = 0, odd = 1;
    while(even < n && odd < n){
        if(inp[n - 1] % 2 == 1){
            swap(inp[odd], inp[n - 1]);
            odd += 2;
        }
        else{
            swap(inp[even], inp[n - 1]);
            even += 2;
        }
    }
    for(int i = 0; i < n; i++){
        printf("%d ",inp[i]);
    }
    return 0;
}
思想很简单：就是设置两个指针，一个是偶地址，一个是奇地址， 判断最后一位是奇数还是偶数，进行移位
发表于 2020-04-30 15:47:52 回复(0)
Java
绚都头像 绚都 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = Integer.parseInt(sc.nextLine().trim());
            String[] s = sc.nextLine().trim().split(" ");
            int[] arr=new int[n];
            for (int i = 0; i < n; i++) {
                arr[i]=Integer.parseInt(s[i]);
            }
            new Solution().adjustArray(arr);
            for (int i = 0; i < n; i++) {
                if(i==n-1) System.out.println(arr[i]);
                else System.out.print(arr[i]+" ");
            }
        }
    }
}

class Solution {
    public void adjustArray(int[] arr){
        int count=0;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]%2!=0) count++;
        }
        if(count>arr.length/2) adjustArray0(arr);
        else{
            int i=0;
            int j=0;
            while(i<arr.length&&j<arr.length){
                while (i<arr.length&&arr[i]%2!=0||i%2==0) i++;   //找到下标为奇数的偶数
                while (j<arr.length&&arr[j]%2==0||j%2!=0) j++;   //找到不符合条件的奇数
                if(i<arr.length&&j<arr.length){
                    arr[i]^=arr[j];
                    arr[j]^=arr[i];
                    arr[i]^=arr[j];
                    i++;
                    j++;
                }
            }
        }
    }

    public void adjustArray0(int[] arr){
        int i=0;
        int j=0;
        while(i<arr.length&&j<arr.length){
            while (i<arr.length&&arr[i]%2==0||i%2!=0) i++;   //找到下标为偶数的奇数
            while (j<arr.length&&arr[j]%2!=0||j%2==0) j++;   //找到不符合条件的偶数
            if(i<arr.length&&j<arr.length){
                arr[i]^=arr[j];
                arr[j]^=arr[i];
                arr[i]^=arr[j];
                i++;
                j++;
            }
        }
    }
}

发表于 2022-04-27 15:24:13 回复(0)
一点浩然气千里快哉风头像 一点浩然气千里快哉风
Go 语言的解法
package main

import (
    "bufio"
    "os"
    "fmt"
    "strings"
    "strconv"
)

func swapElem(nums []int64){
    single, double := 1, 0
    var i int64 = 0
    for ;single < len(nums)&&double <len(nums);{
        if ((nums[i] - i) % 2 + 2)%2== 0{
            i++
            continue
        }
        if nums[i] % 2 == 1{
            nums[i], nums[single] = nums[single], nums[i]
            single += 2
        }else{
            nums[i], nums[double] = nums[double], nums[i]
            double += 2
        }
    }
}

func main(){
    var num int64
    fmt.Scan(&num)
    source := make([]int64, num)
    input := bufio.NewScanner(os.Stdin)
    bs := make([]byte, 2000*1024)
    input.Buffer(bs, len(bs))
    input.Scan()
    scanStr := strings.Split(input.Text(), " ")
    for i:=0; i<len(scanStr); i++{
        temp, _ := strconv.Atoi(scanStr[i])
        source[i] = int64(temp)
    }
    
    swapElem(source)
    for i:=0; i<len(source); i++{
        fmt.Printf("%v ", source[i])
    }
    
    
}

发表于 2021-08-20 21:23:37 回复(0)
Python
毓毓子最可爱头像 毓毓子最可爱 
#数位调整函数
def process(nums):
    #偶数下标
    even=0
    #奇数下标
    odd=1
    #以最后一个数字为过渡，交换奇数位，偶数位上的数字
    while even<len(nums)and odd<len(nums):
        #如果最后一个数字是偶数
        #应该放在偶数位置上
        if nums[-1]%2==0:
            #交换数值
            nums[even],nums[-1]=nums[-1],nums[even]
            #偶数位置前移
            even+=2
        else:
            nums[odd],nums[-1]=nums[-1],nums[odd]
            odd+=2
    return nums

n=int(input())
nums=list(map(int,input().split()))

print(" ".join(map(str,process(nums))))


发表于 2021-06-11 09:22:44 回复(0)
胡牛客头像 胡牛客 
import java.util.*;
public class Main {
    public static void main(String[]args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int[]arr  = new int[N];
        for(int i = 0; i < N; i++){
            arr[i] = scan.nextInt();
        }
        adjust(arr);
        for(int i = 0; i < N; i++){
            System.out.print(arr[i] + " ");
        }
    }
    public static void adjust(int[] arr) {
        int oddCur = 1;
        int evenCur = 0;
        int len = arr.length;
        while (true) {
            while (oddCur < len && (arr[oddCur] & 1) != 0) {
                oddCur += 2;
            }
            if (oddCur >= len) break;
            while (evenCur < len && (arr[evenCur] & 1) == 0) {
                evenCur += 2;
            }
            if (evenCur >= len) break;
            swap(arr, oddCur, evenCur);
        }
    }
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

发表于 2021-06-10 12:00:43 回复(0)
斐波那契额头像 斐波那契额 
const N = Number(readline());
const arr = readline().split(' ').map(Number);

let even = 0; // 指向arr最左边的偶数下标，而且始终指向偶数下标
let odd = 1; // 指向arr最左边的奇数下标，而且始终指向奇数下标
// 依次判断arr[N - 1]是奇数还是偶数，是奇数就和odd位置的值交换，是偶数就和even
// 位置的值交换，随后even或者odd都向右移到下一个奇数或者偶数下标，也就是 even += 2
// 或者 odd += 2
while (even < N && odd < N) {
  if (arr[N - 1] % 2) {
    const tmp = arr[N - 1];
    arr[N - 1] = arr[odd];
    arr[odd] = tmp;
    odd += 2;
  } else {
    const tmp = arr[N - 1];
    arr[N - 1] = arr[even];
    arr[even] = tmp;
    even += 2;
  }
}
console.log(arr.join(' '));

发表于 2021-03-29 22:02:28 回复(0)
C/C++
codewind头像 codewind 
#include<iostream>
using namespace std;
const int N = 1e5+3;
int a[N];
int n;
 

int main() {
    scanf("%d", &n);
    for(int i=0;i<n;++i) scanf("%d", a+i);
    int even = 0,odd = 1;
    while (even <n && odd <n) {
        if(a[n-1]&1) {
            swap(a[odd],a[n-1]);
            odd+=2;
        }else {
            swap(a[even],a[n-1]);
            even+=2;
        }
    }
    for(int i=0;i<n;++i) printf("%d ", a[i]);
    return 0;
    
    
    
}

发表于 2021-01-30 22:57:00 回复(0)
夏花爱秋叶头像 夏花爱秋叶 
var n=parseInt(readline())
var old=readline().split(' ').map(Number)
// 先把数组按照奇数，偶数进行分类，然后再根据数量进行填充
// 也就是不鸟题目说的复杂度。。。
var one=[],two=[];
for(var i=0;i<n;i++){
    if(old[i]%2==0){
        two.push(old[i])
    }else{
        one.push(old[i])
    }
}
var arr=[];
for(var j=0;j<n;j++){
    if(j%2==0){
        // 需要判断，如果偶数用完了，那就用奇数
        if(two[0]){
            arr.push(two[0])
            two.shift() 
        }else{
            arr.push(one[0])
            one.shift()
        }
    }else{
        if(one[0]){
            arr.push(one[0])
            one.shift() 
        }else{
            arr.push(two[0])
            two.shift()
        }
    }
}
console.log(arr.join(' '))

发表于 2020-04-17 23:31:07 回复(0)
JaniceWu头像 JaniceWu 
import sys

def main():
	N = int(sys.stdin.readline().strip())
	arr = list(map(int,sys.stdin.readline().strip().split()))
	even = []
	odd = []
	for i in range(N):
		if arr[i]%2==0:
			even.append(arr[i])
		else:
			odd.append(arr[i])
	minlen = min(len(even),len(odd))
	res = [0]*minlen*2
	for i in range(minlen):
		res[i*2] = even[i]
		res[i*2+1] = odd[i]
	if len(even)>len(odd):
		res.extend(even[len(odd):])
	else:
		res.extend(odd[len(even):])
	print(' '.join(map(str,res)))
main()

发表于 2020-04-07 17:11:59 回复(0)
zhy201908170031157头像 zhy201908170031157 
int main(){
    int n;
    scanf("%d", &n);
    int arr[n];
    for(int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }

    int odd = 1, even = 0;

    while(true){
        while(arr[odd] % 2){ // 找到下一个错位的奇数
            odd += 2;
        }
        
        while(!(arr[even] % 2)){ // 找到下一个错位的偶数
            even += 2;
        }
        
        if(odd < n && even < n){
            swap(arr[even], arr[odd]);
        } else {
            break;
        }
    }

    for(int i = 0; i < n; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");

    return EXIT_SUCCESS;
}
不用考虑奇数偶数的长短，直接把错位的交换位置就行了
发表于 2019-11-15 01:55:07 回复(0)
勇敢的打工人头像 勇敢的打工人 
#include <bits/stdc++.h>
using namespace std ;
const int MAXN = 1e5+5;
int a[MAXN];
int main()
{
    int n; cin>>n;
    for(int i=0; i<n; i++) cin>>a[i];
    int l = 0, r = 1;
    while(l < n && r < n) {
        if(a[l] & 1) {
            if(a[r] & 1) r += 2;
            else {
                swap(a[l], a[r]);
                l += 2;
            }
        }
        else l += 2;
    }
    for(int i=0; i<n; i++) cout<<a[i]<<" ";
    cout<<endl;
    return 0;
}

发表于 2019-09-26 20:15:13 回复(0)
JavaScript
瑞奇头像 瑞奇 
let readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
const lines = [];
rl.on("line", function(line) {
    //将输入放到新建的空数组中
    lines.push(line);
    //判断，如果输入的行数等于某一值时
    if (lines.length === 2){
        //通过数组索引分别得到数组中每一行的数据，并做相应操作
        const num1 = lines[0].split(' ');
        const num2 = lines[1].split(' '); 
        let outArr =new Array(num1[0]);
        let odd = 1; // 奇数下标
        let even = 0; // 偶数下标
        for (let i = 0; i < num1[0]; i++) {
            if (num2[i] % 2 == 0) {
                outArr[even] = num2[i];
                even += 2;
            }else{
                outArr[odd] = num2[i];
                odd += 2;
            }
        }
        console.log(outArr);
        rl.close();
    }
});
发表于 2019-08-23 23:58:25 回复(0)
黑麦威士忌头像 黑麦威士忌 
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = Integer.parseInt(in.nextLine());
        int[] arr = new int[N];
        int ouCount =0, jiCount=0;
        for (int i = 0; i < N; i++) {
            arr[i] = in.nextInt();
            if ((arr[i] & 1) == 0) {
                ouCount++;
            } else {
                jiCount++;
            }
        }
        /*假如奇数个数大于偶数，那么奇数应该占据所有的奇数位，且要去抢
        偶数位，其实我们只需要将奇数位上的偶数换成偶数位上的奇数就可以了。
        p1从index=0开始用来指向奇数位上的偶数。
        p2从index=0开始用来指向偶数位上的奇数。*/
        int p1 = 0;
        int p2 = 0;
        if(jiCount > ouCount){
            for (int i = 0; i < N; i++) {
                //在下标i处找到奇数位上的偶数
                if(i % 2 == 1 && arr[i] % 2 == 0){
                    p1 = i;
                    //接下来从头开始找偶数位上的奇数进行交换
                    for (int j = p2; j < N; j++) {
                        if(j % 2 == 0 && arr[j] % 2 == 1){
                            p2 = j;
                            swap(arr, p2, p1);
                            break;
                        }
                    }
                }
            }
        }else {
            /*偶数个数大于奇数，那么偶数应该占据所有的偶数数位，且要去抢
            奇数位，其实我们只需要将偶数位上的奇数换成奇数位上的偶数就可以了。
            p1从index=0开始用来指向奇数位上的偶数。
            p2从index=0开始用来指向偶数位上的奇数。*/
            for (int i = 0; i < N; i++) {
                //在下标i处找到偶数位上的奇数
                if(i % 2 == 0 && arr[i] % 2 == 1){
                    p2 = i;
                    //接下来从头开始找奇数位上的偶数进行交换
                    for (int j = p1; j < N; j++) {
                        if(j % 2 == 1 && arr[j] % 2 == 0){
                            p1 = j;
                            swap(arr, p2, p1);
                            break;
                        }
                    }
                }
            }
        }

        for (int i = 0; i < N; i++) {
            System.out.print(arr[i] + " ");
        }


    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }



}

发表于 2019-08-23 22:46:59 回复(0)
Python
圣诞节的安徒生头像 圣诞节的安徒生 
N = eval(input())
ls = list(map(int, input().split()))
# 奇数odd 偶数even
odd, even = [], []
for i in ls:
    if i%2 == 1:
        odd.append(i)
    else:
        even.append(i)
# 奇数更多,先放完偶数
if len(odd) > len(even):
    for i in range(len(even)):
        ls[i*2] = even[i]
        ls[i*2+1] = odd[i]
    ls[2*len(even):] = odd[len(even):]
else:
    for i in range(len(odd)):
        ls[i*2] = even[i]
        ls[i*2+1] = odd[i]
    ls[2*len(odd):] = even[len(odd):]
print(' '.join(map(str, ls)))

发表于 2019-08-13 16:04:24 回复(0)
提交观点

问题信息

模拟
上传者：小小
难度：
18条回答 5729浏览

热门推荐

通过挑战的用户

查看代码

相关试题

奇数下标都是奇数或者偶数下标都是偶数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号