欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数组常见编程题

程序员文章站 2022-05-25 16:33:21
1. 重新排列数列,使得数组左边为奇数,右边为偶数 空间复杂度O(1) 时间复杂度O(n) 思路:两个指针分别指向数组的头和尾,头指针正向遍历数组,找到第一个偶数 尾指针反向遍历数组,找到第一个奇数,两者交换 2. 如何找出数组中唯一的重复元素 每个数组只能访问一次,不能用辅助空间 数组a[n] 数 ......

1. 重新排列数列,使得数组左边为奇数,右边为偶数

空间复杂度O(1) 时间复杂度O(n)

思路:两个指针分别指向数组的头和尾,头指针正向遍历数组,找到第一个偶数

尾指针反向遍历数组,找到第一个奇数,两者交换

void permu(vector<int>& a,int& n)
{
    int i=0,j=n-1;
    while(i<j)
    {
        while(a[i]%2==1&&j>i) i+=1;
        while(a[j]%2==0&&j>i) j-=1;
        swap(a[i],a[j]);
    }
}

int main()
{
    int n;
    cin>>n;
    vector<int> a(n,0);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }

    permu(a,n);
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<ends;
    }
    return 0;
}

2. 如何找出数组中唯一的重复元素

每个数组只能访问一次,不能用辅助空间

数组a[n] 数的取值范围:1~n-1

思路:异或法,设重复的数为A,剩下的数异或的结果是B,异或的性质A^A=0 0^A=A

A^B^A^A^B=A

int dup_elem(vector<int>& a,int& n)
{
    int res=0;
    for(int i=0;i<n;i++)
    {
        res^=a[i];
    }
    for(int i=1;i<n;i++)
    {
        res^=i;
    }
    return res;
}

int main()
{
    int n;
    cin>>n;
    vector<int> a(n,0);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int res=0;
    res=dup_elem(a,n);
    cout<<res<<endl;
    return 0;
}

 

3. 已知大小分别为m、n的两个无序数组对A、B 和一个常数c

求满足A[i]+B[j]=c的所有A[i]和B[j]

#include <iostream>
#include <map>
#include <vector>

using namespace std;

void print_all_arr(vector<int>& a,vector<int>& b,int& m,int& n,int& sum)
{
    map<int,bool> mp;
    vector<int> smaller(a);
    vector<int> bigger(b);
    int nsmaller=(m>=n)?n:m;
    int nbigger=(m>=n)?m:n;
    if(m>n)
    {
        smaller=b;
        bigger=a;
    }
    for(int i=0;i<nsmaller;i++)
    {
        mp.insert(pair<int,bool>(smaller[i],true));
    }
    for(int i=0;i<nbigger;i++)
    {
        if(mp.find(sum-bigger[i])!=mp.end())
        {
            cout<<"("<<bigger[i]<<","<<sum-bigger[i]<<")"<<endl;
        }
    }
}

int main()
{
    int sum,m,n;
    cin>>sum>>m>>n;
    vector<int> a(m,0);
    vector<int> b(n,0);
    for(int i=0;i<m;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<n;i++)
    {
        cin>>b[i];
    }
    print_all_arr(a,b,m,n,sum);

    return 0;
}