xiaoxipan
BAN USERthe space complexity is O(1) however the time complexity is O(32*n). Even O(32*n) is also O(n), actually since 32 >= logn, this is bigger than O(n*logn), which means actually we can just sort. So still looking for a real O(n) approach.
By the way, I tried to delete my post but always failed.
Inspired by Phoenix's solution I found another solution that doesn't need to alter the input array. I put all the code here: 1. My solution; 2 Solution based on Phoenix's 3 test cases:
#include <time.h>
#include <stdlib.h>
#include <assert.h>
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
int firstBit1( int x ){
//given x, return the index of the first 1 bit of x
for( int i = 0; x ; x >>= 1, ++i ){
if( x&1 )//test whether the i-th bit of x is 1
return i;
}
return -1;
}
bool find2( std::vector<int> &arr, int &a, int &b, int skip ){
//given a, b occur odd times in arr, others occur even times, return a, b
//with the extra condition: skip all elements that equal to "skip"
int x = 0;
for( int v : arr ){
if( v==skip )continue;
x ^= v;
}
int bit = firstBit1( x );
if( bit == -1 )return false;//invalid input
a = b = 0;
int mask = (1<<bit);
for( int v : arr ){
if( v==skip )continue;
if( v&mask )a ^= v;
else b^= v;
}
return true;
}
bool found( std::vector<int> &arr, int a ){
//check whether "a" occurs odd times in arr
bool odd = false;
for( int v : arr )if( v==a )odd = !odd;
return odd;
}
bool find3( std::vector<int> &arr, int &a, int &b, int &c ){
a = b = 0;
int bits = sizeof(int)*8;
for( int i = 0;i < bits; ++ i ){
int mask = (1<<i);
for( int v : arr ){
if( v&mask )a ^= v;
else b^= v;
}
if( found(arr, a) ){
return find2( arr, b, c, a );
}
else if( found(arr, b) ){
return find2( arr, a, c, b );
}
}
return false;
}
void createTestCase( std::vector<int> &arr, int &a, int &b, int &c ){
//3 different numbers a, b, c
int max = 10, max_occur = 10;
b = rand()%max;
if( b == 0 || b==max-1 )b = max/2;
a = rand()%b;
c = b + 1 + rand()%(max-1-b);
std::vector<int> different_numbers(max, 0);
different_numbers[a] = (2*(rand()%max_occur)+1)%max_occur;
different_numbers[b] = (2*(rand()%max_occur)+1)%max_occur;
different_numbers[c] = (2*(rand()%max_occur)+1)%max_occur;
int n = 0;
for( int i = 0;i < max; ++ i ){
if( different_numbers[i] == 0 ){
different_numbers[i] = (2*(rand()%max_occur))%max_occur;
}
n += different_numbers[i];
}
arr.resize(n);
for( int i = 0, k = 0; i < max; ++ i ){
for( int j = 0;j < different_numbers[i]; ++ j ){
arr[k++] = i;
}
}
std::random_shuffle( arr.begin(), arr.end() );
}
void bitBasedGroup( std::vector<int>::iterator from, std::vector<int>::iterator to, int bit, int max_bits ){
if( bit == max_bits || to <= from )return;
auto bit0_it = from - 1;
int mask = (1<<bit);
for( auto it = from; it != to; it ++ ){
if( 0 == (mask & *it) ){
std::swap( *it, *(++bit0_it) );
}
}
// for( auto it = from; it != to; it ++ )std::cout << *it << ' ';
// std::cout << std::endl;
++ bit0_it;
bitBasedGroup( from, bit0_it, bit+1, max_bits );
bitBasedGroup( bit0_it, to, bit+1, max_bits );
}
void printArray( std::vector<int> &arr ){
std::cout << '[';
for( int v : arr ) std::cout << v << ' ';
std::cout << ']' << std::endl;
}
void bitBasedGroup( std::vector<int> &arr ){
int max = *std::max_element( arr.begin(), arr.end() );
int bits = 0;
for( ; max; max >>=1 ) ++ bits;
bitBasedGroup( arr.begin(), arr.end(), 0, bits );
}
bool find3ByGroup( std::vector<int> &arr, int &a, int &b, int &c ){
if( arr.size() < 3 )return false;
bitBasedGroup( arr );
int X[3], found = 0;
int prev = arr[0];
bool odd = true;
for( int i = 1;i < arr.size(); ++ i ){
int v = arr[i];
if( v == prev ){
odd = !odd;
}
else{
if( odd && found<3 )X[found++] = prev;
prev = v; odd = true;
}
}
if( odd && found<3 )X[found++] = prev;
if( found != 3 )return false;
a = X[0]; b = X[1]; c = X[2];
return true;
}
int main(){
srand( time(0) );
for( int i = 0;i < 1000; ++ i ){
int X[3];
std::vector<int> arr;
createTestCase( arr, X[0], X[1], X[2] );
printArray( arr );
std::cout << "a:" << X[0] << ' ' << "b:" << X[1] << ' ' << "c:" << X[2] << std::endl;
int Y[3];
find3( arr, Y[0], Y[1], Y[2] );
std::sort( Y, Y+3 );
assert( std::equal(X,X+3,Y) );
find3ByGroup( arr, Y[0], Y[1], Y[2] );
printArray( arr );
std::sort( Y, Y+3 );
assert( std::equal(X,X+3,Y) );
}
}
This algorithm works well with time complexity O(M)+O(M/2)+...+O(1)=O(M), and space complexity O(1). It is the best solution till now. Please up vote Anonymous' answer.
The code and the test case:
#include <assert.h>
#include <time.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <algorithm>
int Solve( std::vector<int> &arr ){
int m = arr.size(), max = 0;
for( int low = 0, high = arr.size(); low < high; ){
int n = (low+high)/2;
std::nth_element( arr.begin()+low, arr.begin()+n, arr.begin()+high,
[](const int &a, const int &b){ return a>b; } );
//now arr[0..n-1] >= arr[n], arr[n+1...] <= arr[n]
if( arr[n] >= n+1 ){
max = std::max( max, n+1 );
low = n+1;
}
else {
high = n;
}
}
return max;
}
int SolveSlow( std::vector<int> &arr ){
std::sort( arr.begin(), arr.end(), [](const int &a, const int &b){ return a>b; } );
for( int n = arr.size() ; n > 0; --n ){
if( arr[n-1] >= n )
return n;
}
return 0;
}
int main(){
srand( time(0) );
int length = 1000;
for( int i = 0;i < 1000; ++ i ){
int m = length;
std::vector<int> arr(m);
for( int j = 0;j < m; ++ j ){
arr[j] = rand()%(length*2);
}
std::vector<int> aArr = arr;
int n1 = SolveSlow( arr );
int n2 = Solve( aArr );
assert( n1 == n2 );
}
return 0;
}
Could you be a bit more detailed on "We can ignore half the elements already considered, so O(M) time algorithm"?
Did you mean that when do selection, we can shrink the search range? I don't understand this. Since the array is not sorted, the n-th element can occur in any place of the array, which means the "selection" algorithm will always have to search the entire array.
Am I missing anything here?
char[] s1 = str1.toCharArray();
char[] s2 = str2.toCharArray();
System.out.println( Arrays.toString(s1) );
int n = s1.length;
for( int i = 0;i < n; ++ i ){
if( s1[i]!=s2[i] ){
int j = i+1;
for( ; j < n && s1[j] != s2[i]; ++ j );
//now s1[j] == s2[i]
for( ; j > i; -- j ){
swap( s1, j, j-1 );
System.out.println( Arrays.toString(s1) );
}
}
}
@Kallu: note the array is sorted, and we only need to search an element a[i] from the array such that a[i]-a[i-1] not equal to the common distance "diff".
What Simon did is different: he tries to find an interval [i,j] such that a[j]-a[i] is not equal to "diff*(j-i)".
[2,1,0,-1,-2] means: boy[0] gives 2 apples to boy[1] and boy[4] each. Then boy[1] gives 1 apple to boy[2]. boy[4] give 1 apple to boy[3].
2 is the median of [4,3,2,1,0]. So we need to subtract [2,2,2,2,2] from that.
for [1,1,1,1,2,1,0,2,1,0,1,1,1,1], the initial flow is:
[0, 0, 0,0,1,1,0,1,1,0,0,0,0,0]
That is: boy[4] gives 1 apple to boy[5], boy[5] passes it to boy[6], and so on.
The median of this array is 0, which means we need to subtract [0,0,....,0] from it, which means we don't need to update this initial solution. It is already optimal.
Note that for all applicable solutions( not necessarily the minimal one), they share the same property: the net flow for each child is invariant.
So two solutions differ from a flow whose net flow for each child vanishes, that is, a circumfluence like 1->1->...->1.
To find the minimal solution, just start from any initial solution, subtract a circumfluence from it, to minimize the difference between the number of positive edges and negative edges. The constant flow in the circumfluence is the median of the flows in the initial solution.
Take [5,0,0,0,0] as an example, an initial flow is [4,3,2,1,0], with 10 steps. subtract the circumfluence [2,2,2,2,2] from it, we get a flow [2,1,0,-1,-2], with 6 steps. This is the minimal solution since it has equal number of positive edges and negative edges: 2.
The time complexicity is O(n).
I realized that no_bits is typically 32( or 64) which is bigger than logn. So it's not better than a sort algorithm which is O(n*logn)
- xiaoxipan July 02, 2014