有一個數(shù)組長度為N,里面的N個數(shù)的范圍是[1, N-1]，因此必有數(shù)是重復出現(xiàn)的。求一個算法找出這個數(shù)，要求時間復雜度為O(n),空間復雜度為O(1)。
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a[]={1,2,4,3,6,3,4};
int tmp,tmp2;
tmp=a[0];
while(1)
{
if(a[tmp]!=-1)
{
tmp2=a[tmp];
a[tmp]=-1;
tmp=tmp2;
}
else break;
}
printf("%d\n",tmp);
}
用兩個棧實現(xiàn)隊列
#include<iostream>
#include<stack>
using namespace std;
stack<int>stackA,stackB;
void enqueue(int x)
{
stackA.push(x);
}
int dequeue()
{
if(stackB.empty())
{
while(!stackA.empty())
{
stackB.push(stackA.top());
stackA.pop();
}
}
if(stackB.empty())
return -1;
int val=stackB.top();
stackB.pop();
return val;
}
int main()
{
char ch;
int i=0;
while(cin>>ch)
{
if(ch=='e')
{
enqueue(i++);
}
else cout<<dequeue()<<endl;
}
}
題目概述：有一個沒有排序，元素個數(shù)為2N的正整數(shù)數(shù)組。要求把它分割為元素個數(shù)為N的兩個數(shù)組，并使兩個子數(shù)組的和最接近。
假設數(shù)組A[1..2N]所有元素的和是SUM。模仿動態(tài)規(guī)劃解0-1背包問題的策略，令S(k, i)表示前k個元素中任意i個元素的和的集合。顯然：
S(k, 1) = {A[i] | 1<= i <= k}
S(k, k) = {A[1]+A[2]+…+A[k]}
S(k, i) = S(k-1, i) U {A[k] + x | x屬于S(k-1, i-1) }
按照這個遞推公式來計算，最后找出集合S(2N, N)中與SUM最接近的那個和，這便是答案。這個算法的時間復雜度是O(22N).
因
為這個過程中只關注和不大于SUM/2的那個子數(shù)組的和。所以集合中重復的和以及大于SUM/2的和都是沒有意義的。把這些沒有意義的和剔除掉，剩下的有
意義的和的個數(shù)最多就是SUM/2個。所以，我們不需要記錄S(2N,N)中都有哪些和，只需要從SUM/2到1遍歷一次，逐個詢問這個值是不是在
S(2N,N)中出現(xiàn)，第一個出現(xiàn)的值就是答案。我們的程序不需要按照上述遞推公式計算每個集合，只需要為每個集合設一個標志數(shù)組，標記SUM/2到1這
個區(qū)間中的哪些值可以被計算出來。關鍵代碼如下：
for(i = 0; i < N+1; i++)
for(j = 0; j < sum/2+1; j++)
flag[i][j] = false;
flag[0][0] = true;
for(int k = 1; k <= 2*N; k++) {
for(i = k > N ? N : k; i >= 1; i--) {
//兩層外循環(huán)是遍歷集合S(k,i)
for(j = 0; j <= sum/2; j++) {
if(j >= A[k] && flag[i-1][j-A[k]])
flag[i][j] = true;
}
}
}
for(i = sum/2; i >= 0; i--) {
if(flag[N][i]) {
cout << "minimum delta is " << abs(2*i - sum) << endl;
break;
}
}
|