antoinedematteo
BAN USERThe first items being already sorted, your proof is false. It can ieasily be done in O(N) time.
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
public class SorteTuple {
public static void main(String[] args) {
// TODO Auto-generated method stub
ThreeTuple t1 = new ThreeTuple( "a" , 2 , 3 );
ThreeTuple t2 = new ThreeTuple( "b" , 3 , 7 );
ThreeTuple t3 = new ThreeTuple( "c" , 5 , 6 );
ThreeTuple t4 = new ThreeTuple( "d" , 8 , 12 );
ThreeTuple t5 = new ThreeTuple( "e" , 10 , 13 );
ThreeTuple t6 = new ThreeTuple( "f" , 12 , 15 );
ThreeTuple t7 = new ThreeTuple( "g" , 17 , 18 );
ArrayList<ThreeTuple> L3 = new ArrayList<ThreeTuple>();
L3.add(t1);L3.add(t2);L3.add(t3);
L3.add(t4);L3.add(t5);L3.add(t6);
L3.add(t7);
LinkedList<TwoTuple> L2 = Sort( L3 );
Iterator<TwoTuple> itr = L2.iterator();
while( itr.hasNext()){
System.out.println( itr.next().toString());
}
}
public static LinkedList<TwoTuple> Sort( ArrayList<ThreeTuple> L3){
LinkedList<TwoTuple> L2 = new LinkedList<TwoTuple>();
ThreeTuple current3Tuple = L3.get(0);
TwoTuple current2Tuple = new TwoTuple( current3Tuple.id , current3Tuple.min);
TwoTuple tempTuple = new TwoTuple( current3Tuple.id , current3Tuple.max);
L2.add( current2Tuple );
for( int i = 1 ; i < L3.size() ; i++ ){
current3Tuple = L3.get(i);
if( tempTuple.val <= current3Tuple.min ){
L2.add( new TwoTuple( tempTuple.id , tempTuple.val) );
L2.add( new TwoTuple( current3Tuple.id , current3Tuple.min));
tempTuple.id = current3Tuple.id;
tempTuple.val = current3Tuple.max;
}
else{
if( tempTuple.val > current3Tuple.min ){
L2.add( new TwoTuple( current3Tuple.id , current3Tuple.min));
}
if( tempTuple.val > current3Tuple.max ){
L2.add( new TwoTuple( current3Tuple.id , current3Tuple.max));
}
if( tempTuple.val > current3Tuple.min && tempTuple.val < current3Tuple.max ){
L2.add( new TwoTuple( tempTuple.id , tempTuple.val));
tempTuple.id = current3Tuple.id;
tempTuple.val = current3Tuple.max;
}
}
}
L2.add( tempTuple );
return L2;
}
public static class TwoTuple{
String id;
int val;
public TwoTuple( String id , int val ){
this.id = id;
this.val = val;
}
public String toString( ){
String s = id+ " - " + val;
return s;
}
}
public static class ThreeTuple{
String id;
int max;
int min;
public ThreeTuple( String id , int min , int max ){
this.id = id;
this.min = min;
this.max = max;
}
}
}
Using Dyanmic programming.
If you know that you have N_{1,n} number finishing with 1 of length n ... N_{9,n} numbers finishing with 9 of length n, then for instance
N_{2,n+1} = N_{6,n}+N_{7,n}+N_{8,n} + N_{9,n}
public class countNumbers {
public static void main(String[] args) {
int n = 5;
int res = howMany( n );
System.out.println( res );
}
static int howMany( int n ){
int[][] tabRes = new int[n][9];
for( int i = 0 ; i < 9 ; i++) tabRes[0][i] = 1;
for( int i = 1 ; i < n ; i++){
for( int j = 0 ; j < 4 ; j++ ){
tabRes[ i ][ j ] = sumArray( tabRes , i - 1, 4 + j , 8 );
tabRes[ i ][ 8 - j ] = sumArray( tabRes , i - 1, 0 , 4-j);
}
tabRes[ i ][ 4 ] = tabRes[ i - 1][ 0 ] + tabRes[ i - 1][ 8 ];
}
return sumArray( tabRes , n-1 , 0 , 8 );
}
static int sumArray( int[][] array , int idxRow , int first , int last ){
int res = 0;
for( int i = first; i<= last ; i++){
res += array[ idxRow ][ i ];
}
return res ;
}
}
My solution works without recursion, in O(n) time and O(1) memory.
It proceeds as follows, by steps
Consider the string "a1b2c3d4e5f6g7h8"
1) Handle groups of 2 -> ab12cd34ef56gh78
2) Handle groups of 4 -> abcd1234efgh5678
3) Handle groups of 8 -> abcdefgh12345678
My code works only for sizes of strings power of 2 and would require some additional code to handle any size but the main idea is there
- antoinedematteo August 17, 2015