首页 > 试题广场 >

数组操作

[编程题]数组操作
  • 热度指数:13918 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
输入一个无序整数数组,调整数组中数字的顺序, 所有偶数位于数组的前半部分,使得所有奇数位于数组的后半部分。
要求时间复杂度为O(n)。

输入描述:
给定无序数组。
长度不超过1000000。


输出描述:
所有偶数位于数组的前半部分,所有奇数位于数组的后半部分。
如果有多个答案可以输出任意一个正确答案。
示例1

输入

2 4 5 7 8 1

输出

2 4 8 7 5 1

备注:
请自觉使用O(n)的算法。
400多ms..............................
#include <iostream>
#include <list>
using namespace std;

int main(){
    list<int> ls;
    int val;
    while(cin >> val){
        if(val % 2 == 0){
            //偶数
            ls.push_front(val);
        } else{
            ls.push_back(val);
        }
    }
    for(list<int>::iterator it = ls.begin(); it != ls.end(); ++it){
        cout << *it << ' ';
    }
    cout << endl;
    return 0;
}


编辑于 2020-06-03 16:11:17 回复(0)
""""
借鉴快速排序的思想,时间复杂度O(n),空间复杂度O(1)
"""

if __name__ == "__main__":
    a = list(map(int, input().strip().split()))
    i, j = 0, len(a) - 1
    while True:
        while i < len(a) and a[i] & 1 == 0: i += 1
        while j >= 0 and a[j] & 1 == 1: j -= 1
        if i >= j: break
        a[i], a[j] = a[j], a[i]
    print(' '.join(map(str, a)))

编辑于 2019-07-14 11:00:58 回复(0)
// 时间 O(n),空间O(1)
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 10;
int arr[maxn];
int n;

void partition() {
    int lo = -1;
    int cur = 0;
    while (cur < n) {
        if (~arr[cur] & 1) swap(arr[++lo], arr[cur]);
        ++cur;
    }    
}

int main() {
    while (scanf("%d", &arr[n]) == 1) ++n;
    partition();    

    for (int i = 0; i < n; ++i) 
        printf("%d%c", arr[i], (i == n - 1 ? '\n' : ' '));
    return 0;
}
编辑于 2019-08-17 23:18:43 回复(0)
双指针求解,当左边是偶数的时候,符合题意,右移左指针;当右边是奇数的时候,符合题意,左移右指针。如果遇到了奇数在偶数之前的情况,就交换这两个数。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strArr = br.readLine().trim().split(" ");
        int[] arr = new int[strArr.length];
        for(int i = 0; i < arr.length; i++) arr[i] = Integer.parseInt(strArr[i]);
        int left = 0, right = arr.length - 1;
        while(left < right){
            // 左边的数是偶数,右移左指针
            while(left < right && arr[left] % 2 == 0)
                left ++;
            // 右边的数是奇数,左移右指针
            while(left < right && arr[right] % 2 == 1)
                right --;
            // 否则交换左边的奇数和右边的偶数
            if(left < right){
                int temp = arr[right];
                arr[right] = arr[left];
                arr[left] = temp;
            }
        }
        for(int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}


发表于 2021-02-27 15:42:55 回复(0)
#include<iostream>
#include<vector>
using namespace std;
int main()
{
	int x;
	vector<int> v1,v2;
	while(cin>>x)
	{
		if(x%2==0) v1.push_back(x);
		else	   v2.push_back(x);	
	}
	for(vector<int>::iterator it1=v1.begin();it1!=v1.end();it1++) cout<<*it1<<" ";
	for(vector<int>::iterator it2=v2.begin();it2!=v2.end();it2++) cout<<*it2<<" ";
	cout<<endl;
	return 0;	
} 

发表于 2020-08-26 11:18:24 回复(0)

归并排序求解----时间复杂度(O(nlongn))

实现原理与归并排序一样,代码如下:

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

using namespace std;

const int N = 1e6 + 10;

vector<int> arr;

void merge(vector<int> &nums,int l,int r)
    {
        if(l>=r) return ; //只有一个元素
        int mid=(l+r)>>1; //二分
        merge(nums,l,mid), merge(nums,mid+1,r); //计算左右两个区间中的逆序对
        int i=l,j=mid+1; //定义两个指针
        vector<int> temp;
        while(i<=mid&&j<=r) //归并
        {
            if(nums[i] % 2 == 0) temp.push_back(nums[i++]);
            else temp.push_back(nums[j++]); //后面的元素小于前面的元素素

        }
        //无论是i或者是j,元素都比之前的数组要大,所以不可能存在新的逆序,把数组填好就可以了
        while(i<=mid) temp.push_back(nums[i++]); 
        while(j<=r) temp.push_back(nums[j++]);
        i=l;
        for(auto x:temp) nums[i++]=x;
    }



int main()
{
    int x;
    while(cin >> x) {
        arr.push_back(x);
        if(cin.get() == '\n') break;
    }
    merge(arr, 0, arr.size() - 1);
    for (int j = 0; j < arr.size(); j ++ ) printf("%d ", arr[j]);

    return 0;
}
发表于 2020-03-09 09:39:10 回复(0)
class Solution(object):
    def order(self):
        #获取输入的整数列表
        array = list(map(int,input().split(' ')))
         #用空间换取时间,建一个列表来保存结果
        res = []
        for i in array:
            #把偶数找出来放到res列表里
            if i%2==0:
                res.append(i)
        for i in array:
            #再把奇数找出来尾插到res列表里
            if i%2==1:
                res.append(i)
        print(" ".join(map(str,res)))
s = Solution()
s.order()

发表于 2019-12-02 18:22:12 回复(0)
Java一直超时的老哥有吗
发表于 2019-11-09 23:12:04 回复(2)
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    getline(cin,s);
    istringstream ss(s);
    vector<int> a,b;
    int x;
    while(ss>>x){
        if(x&1)
            b.push_back(x);
        else
            a.push_back(x);
    }
    int cnt = 1, n = a.size(), m = b.size();
    for(int i=0;i<n;i++){
        if(i==n+m)
            cout<<a[i]<<endl;
        else
            cout<<a[i]<<" ";
    }
    for(int i=0;i<m;i++){
        if(i==n+m)
            cout<<b[i]<<endl;
        else
            cout<<b[i]<<" ";
    }
    return 0;
} 

发表于 2019-07-17 01:17:45 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    vector<int>num,res1,res2;
    while(cin>>n)
        num.push_back(n);
    for(int i=0;i<num.size();i++)
    {
        if(num[i]%2==0)
            res1.push_back(num[i]);
        else
            res2.push_back(num[i]);
    }
    for(int i=0;i<res1.size();i++)
        cout<<res1[i]<<" ";
    for(int i=0;i<res2.size();i++)
        cout<<res2[i]<<" ";
    return 0;
}

发表于 2019-07-04 11:35:02 回复(0)
n = map(int, raw_input().split())

a, b = [], []

for i in n :
    if i % 2 == 0 :
        a.append(i)
    else : b.append(i)
    pass

a += b

for i in a :
    print i, ;
发表于 2019-07-20 07:58:57 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<int> arr;
    int t;
    while(cin>>t)
        arr.push_back(t);
    int i=0,j=arr.size()-1;
    while(i!=j){
        while(i<j&& !(arr[i]&1) )
            i++;
        while(i<j&& arr[j]&1)
            j--;
        swap(arr[i],arr[j]);
    }
    for(int k=0;k<arr.size();k++)
        cout<<arr[k]<<" ";
    return 0;
}

发表于 2019-11-08 21:05:32 回复(0)
import java.util.Scanner;
public class Main {
	public static void Solution(int[] array) {
		if(array==null||array.length==0) return;
		int low = 0;
		int high = array.length-1;
		while(low<high) {
			while(low<high&&(array[low]&1)==0) {
				low++;
			}
			while(low<high&&(array[high]&1)==1) {
				high--;
			}
			if(low<high) {
				int temp = array[low];
				array[low] = array[high];
				array[high] = temp;
			}
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		String[] strArray = str.split(" ");
		int[] intArray = new int[strArray.length];
		for(int i = 0;i<strArray.length;i++) {
			intArray[i] = Integer.parseInt(strArray[i]);
		}
		Solution(intArray);
		for(int i = 0;i<intArray.length;i++) {
			System.out.print(intArray[i] + " ");
		}
	}
}
提交代码后一直卡在保存代码中,然后点交卷的时候居然通过了🤣🤣
编辑于 2019-09-10 15:38:22 回复(0)
import java.util.Scanner;  public class Test01 { public static void main(String[] args) {
     Scanner scanner = new Scanner(System.in);  String line = scanner.nextLine();  String[] stringArray = line.split(" ");  int[] arr = new int[stringArray.length];  for(int i = 0;i < stringArray.length;i++) {
          arr[i] = Integer.parseInt(stringArray[i]);  } int low = 0;  int high = arr.length-1; while(low < high) { if(arr[low] % 2 == 0) {
                low++;  } if(arr[high] % 2 != 0) {
                high--;  } if(low < high) { int temp = arr[low];  arr[low] = arr[high];  arr[high] = temp;  }
     } for(int i = 0;i <arr.length;i++) {
          System.out.print(arr[i]);  System.out.print(" "); }
  }
}

发表于 2022-09-14 13:23:58 回复(0)
arr=list(map(int,input().split()))
i=0
j=len(arr)-1
while i<j:
    if i<j and arr[i]%2==0:
        i+=1
    if i<j and arr[j]%2==1:
        j-=1
    if i<j:
        arr[i],arr[j]=arr[j],arr[i]
for i in range(len(arr)):
    print(arr[i],end=" ")
    

发表于 2022-03-22 21:34:32 回复(0)
#include <stdio.h>
#include <stdlib.h>

const int N = 1E6;

void swap(int* a, int* b) {
  *a ^= *b;
  *b ^= *a;
  *a ^= *b;
}

int main(const int argc, const char* const argv[]) {
  int nums[N], numsSize = 0;
  while (fscanf(stdin, "%d", nums + numsSize++) != EOF);  
  --numsSize;
  
  int l = 0, r = numsSize - 1;
  while (l < r) {
    while (l < r && !(*(nums + l) & 1)) ++l;
    while (l < r && *(nums + r) & 1) --r;
    if (l < r) swap(nums + l++, nums + r--);
  }
  
  int i;
  for (i = 0; i < numsSize; ++i)
    fprintf(stdout, "%d ", *(nums + i));
  
  return 0;
}

发表于 2021-07-28 11:20:00 回复(0)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector <ll> odd;
vector<ll> even;
ll x;
int main(){
    while(scanf("%lld",&x)!=EOF){
        if(x&1) odd.push_back(x);
        else even.push_back(x);
    }
    even.insert(even.end(),odd.begin(),odd.end());
    for (auto iter = even.cbegin(); iter != even.cend(); iter++)
    { 
        if(iter==even.cbegin()) ;else cout<<" ";
        cout << (*iter);
    }
    cout<<endl;
    return 0;
}

发表于 2021-04-01 08:15:53 回复(0)
def sortArray(arr):
    arr_even = []    # 分别保存偶数和奇数,append的时间复杂度是O(1),insert的时间复杂度是O(n)
    arr_odd = []

    for i in arr:
        if i % 2 == 0:
            arr_even.append(str(i))
        elif i % 2 == 1:
            arr_odd.append(str(i))

    arr_st = " ".join(arr_even+arr_odd)
    return arr_st

arr = map(int, input().strip().split(" "))
print(sortArray(arr))

发表于 2020-09-15 16:07:43 回复(0)
#include<iostream>
#include<vector>
int main()
{
    int n;
    std::vector<int>s;
    std::vector<int>t;
    while(std::cin>>n)
    {
        if(n%2==0)s.push_back(n);
        else t.push_back(n);
    }
    for(int i=0;i<s.size();i++)std::cout<<s[i]<<" ";
    for(int i=0;i<t.size();i++)std::cout<<t[i]<<" ";
    std::cout<<std::endl;
    s.clear();
    t.clear();
    return 0;
}
发表于 2020-09-11 12:02:06 回复(0)