denny.Rongkun
BAN USERpublic class NumWays {
public static int numOfper(int[] num,int target,int low,int high){
int count=0;
if(low>high)
return 0;
if(num[low]==target)
count++;
int zero=numOfper(num,target,low+1,high);
int add=numOfper(num,target-num[low],low+1,high);
int minu=numOfper(num,num[low]+target,low+1,high);
return zero+add+minu+count;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] num={2,4,6,8};
//System.out.println(getNoOfWays(num,0,12));
System.out.println(numOfper(num,12,0,2));
}
}
this return 4,but problem is time complexity: O(3^n)
anyone has better algorithms?
Professional opinion-Generally if the array is unsorted, the most efficient algorithm must be O(n),
First method is calculate the: x+y=c and x.y=d and then figure out x,y just described above.
this needs O(n) time but problem is if N is very large, it must be overflow!!!
Second method is use hash table, build a hash table use array(1,N) and scan from 1.....N to figure out the missing number. Time complexity O(n), space O(n)
public class StringPremutation {
public static void permutation(int[] base,int n,int perlength,int[] perm)
{
int temp;
if(n==0)
{
for(int i=0;i<4;i++)
{
System.out.print(perm[i]);
}
System.out.println();
}
else
{
for(int count=4-n;count<perlength;count++)
{
temp=perm[0];
perm[0]=perm[count];
perm[count]=temp;
permutation(base,n-1,perlength,perm);
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] base={0,1,2,3,4,5,6,7,8,9};
int[] perm=new int[10];
perm=base;
permutation(base,4,10,perm);
}
}
use recursion, divide and conquer
Time complexity:T(n)=10T(n-1)+O(1)
T(n)=O(10^n)
This is simple. but not the best in algorithms, does anyone have better idea?
we can use a array[100], and each element contain two field, one is a integer, say(86) is China and (1) is USA, another field can be a root of B-Tree, storing all the tele numbers of the country if the number is international.
Time complexity: O(logn) for delete , insert and query
randomized quick sort has expected time O(nlogn) and O(N^N) worst case,
- denny.Rongkun March 19, 2013which is also an inplace sort