Tuotuo
BAN USERTest the code below, it is O(n), memory usage O(1). Cheers!!!
#include <iostream>
using namespace std;
void sortoddeven(int * a, int n)
{
int oddcount = 0;
for(int i = 0; i<n; i++)
oddcount += a[i]%2;
int i_e = oddcount;
int i_o = 0;
int i = 0;
while(i_o<oddcount)
{
if(a[i]%2)
swap(a[i++],a[i_o++]);
else
swap(a[i++],a[i_e++]);
if (i==oddcount)
i = i_o;
}
}
int main() {
// your code goes here
int n = 20;
int *a = new int[n];
for(int i = 0; i<n; i++)
a[i] = i;
sortoddeven(a,n);
for(int i = 0; i<n; i++)
cout<<a[i]<<" ";
return 0;
}
Sorry, still seems to have some problem.
- Tuotuo March 02, 2014The diff value is simply 2 times the different between the largest and the smallest num of the three.
So a naive way to do this is move the pointer of array correspond to the smallest num of the three upward by one, and update, till we reach the top or find three identical number.
condition that need to be taken care of is when there is two equal number, then compare and find the smaller one of the two number which are next to the equal number in corresponding array, and update that pointer.
Please comment on my solution, I think it works, Thanks!
int test1s(int n)
{
int num1s = 0;
while(n%10==1)
{
n = n/10;
num1s++;
}
if( n == 0 )
return num1s;
else
return 0;
}
string minmul3(int n)
{
string err = "err";
if (mod(n+10,10)!=3)
return err;
//we are solving the problem by iterative find the digit of b,which satisfies n*b=111....11.
//pre recomputed map[i] = s; st: mod(s*3+i,10) = 1;
int map[] = {7,0,3,6,9,2,5,8,1,4};
int res =0;
int count = 0;
while (test1s(res)==0)
{
count++;
int b = map[res%10];
res = res/10 + b*n;
}
count = count + test1s(res);
string result;
result.resize(count+1);
memset(result.c_str(),'1',count);
result.c_str()[count+1] = 0;
return result;
}
Implementation and Test code.
This one is O(n) complexity,
- Tuotuo January 11, 2015