數組常見編程題

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;
}