xiaofan
BAN USERO(log n) is much faster than O(n/k) if the array length is bigger and k is small.
For example: n=1000, k=10 , O(logn)=10 , but O(n/k)=100.
For the length of n=1000, only the K bigger than 100, O(n/k) better than O(logn).
So no one can make sure O(n/k) is faster than O(log n) .
Below is the java code solution
The first method time complexity is: Θ(n)
The second method average time complexity is: Θ(logn)
:
/**
*
* @author Alex (xiaofan)
*
*/
public class RepetitionsNumber {
/**
* @param args
*/
public static void main(String[] args) {
int[] a = { 1, 2, 2, 3, 3, 3, 4 };
RepetitionsNumber repetitionsNumber =new RepetitionsNumber();
int maxRepNumber=repetitionsNumber
.getBiggestRepetitionsNumber(a);
System.out.println(maxRepNumber);
maxRepNumber = repetitionsNumber
.getBiggestRepetitionsNumberMoreEfficient(a);
System.out.println(maxRepNumber);
}
/**
* Time Complexity Θ(n)
*
* @param a
* @return
*/
public int getBiggestRepetitionsNumber(int[] a) {
int maxRepNumber = 1;
int currentRepNumber = 1;
for (int i = a.length - 1; i > 0; i--) {
int j = i - 1;
if (a[i] == a[j]) {
currentRepNumber++;
} else {
maxRepNumber = maxRepNumber > currentRepNumber
? maxRepNumber: currentRepNumber;
currentRepNumber = 1;
}
}
return maxRepNumber;
}
/**
* Improve one with devide and conquer .
*
* Average Time Complexity Θ(logn) Worst Case Θ(n)
*
* @param a
* @return
*/
public int getBiggestRepetitionsNumberMoreEfficient(int[] a) {
return binaryRepNumber(0, a.length - 1, a);
}
private int binaryRepNumber(int startIndex, int endIndex,int[] a) {
if (startIndex == endIndex) {
return 1;
}
int midIndex = (startIndex + endIndex) / 2;
int midRepNumber = 1;
int leftMidInex = startIndex;
int rightMidIndex = endIndex;
for (int i = midIndex; i > startIndex; i--) {
int j = i - 1;
if (a[i] == a[j]) {
midRepNumber++;
} else {
leftMidInex = j;
break;
}
}
for (int i = midIndex; i < endIndex; i++) {
int j = i + 1;
if (a[i] == a[j]) {
midRepNumber++;
} else {
rightMidIndex = j;
break;
}
}
int leftRepNumber=binaryRepNumber(startIndex,leftMidInex, a);
int rightRepNumber=binaryRepNumber(rightMidIndex,endIndex, a);
int maxRepunumber = leftRepNumber > rightRepNumber
? leftRepNumber: rightRepNumber;
maxRepunumber = maxRepunumber > midRepNumber
? maxRepunumber: midRepNumber;
return maxRepunumber;
}
}
Java Code & Tested
public class Numbers {
/**
* @param args
*/
public static void main(String[] args) {
Numbers numbers=new Numbers();
numbers.printNumbers(3);
//numbers.printNumbers(5);
}
public void printNumbers(int n){
int[] a={1,2,3,4,5,6,7,8,9};
subPrint("",0,n,a);
}
private void subPrint(String preFix,int startIndex,int numberCount,int[] a){
for(int i=startIndex;i<a.length;i++){
int digit=a[i];
if(numberCount==1){
System.out.println(preFix+digit);
}else{
subPrint(preFix+digit,digit,numberCount-1,a);
}
}
}
}
Below is java code:
- xiaofan May 31, 2014