Find next greater number of set digits - Java
import java.util.Arrays;
public class NextGreater {
public static void main(String[] args) {
int [] merg = nextGreater(new int[]{5,3,4,9,7,6});
for(int i = 0; i <= merg.length -1; i++)
System.out.println(merg[i]);
}
public static int[] nextGreater(int[] num){
int invIndex = findInvEle(num);
int nexInvToSwap = findNexInv(invIndex, num);
int[] nums = swap(invIndex, nexInvToSwap, num);
int[] merg = sort(nums, invIndex + 1, nums.length -1);
return merg;
}
//find number which smaller while traversing from left to right
private static int findInvEle(int[] num) {
int invInd = 0;
for(int i = num.length - 1; i >= 1; i--){
if(num[i -1] < num[i]){
invInd = i -1;
break;
}
}
return invInd;
}
//find the next least number after finding the above number and then swap
private static int findNexInv(int invInd,int[] num){
int nxtGrNow = -1;
int nxtGr = -1;
int nxtGrInd = -1;
for(int i = num.length - 1; i > invInd; i--){
if(num[invInd] < num[i]){
nxtGrNow = num[i];
if(nxtGr < nxtGrNow){
nxtGr = nxtGrNow;
nxtGrInd = i;
}
}
}
return invInd + nxtGrInd;
}
private static int[] swap(int invIndex,int nexInvToSwap, int[] num){
int temp = num[invIndex];
num[invIndex] = num[nexInvToSwap];
num[nexInvToSwap] = temp;
return num;
}
//sort all the elements after the inversion number found in the above method after swapping
@SuppressWarnings("null")
public static int[] sort(int[] nums,int invIndex ,int lastIndex){
if(nums.length == 0 || nums.length == 1)
return null;
int [] subArr = Arrays.copyOfRange(nums, invIndex, lastIndex + 1);
quickSort(subArr, 0, subArr.length - 1);
int[] mergerArr = new int[lastIndex + 1];
for(int i = 0; i < invIndex; i++){
mergerArr[i] = nums[i];
}
for(int i = 0; i <= subArr.length - 1; i++){
mergerArr[invIndex + i] = subArr[i];
}
return mergerArr;
}
public static void quickSort(int[] nums,int low ,int high){
int i = low;
int j = high;
int pivot = nums[(low + (high - low + 1))/2];
while(i <= j){
while(pivot > nums[i])
i++;
while(pivot < nums[j])
j--;
if(i <= j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++;
j--;
}
if(low < j)
quickSort(nums,low,j);
if(high > i)
quickSort(nums, i, high);
}
}
}
source: http://www.geeksforgeeks.org/find-next-greater-number-set-digits/
public class NextGreater {
public static void main(String[] args) {
int [] merg = nextGreater(new int[]{5,3,4,9,7,6});
for(int i = 0; i <= merg.length -1; i++)
System.out.println(merg[i]);
}
public static int[] nextGreater(int[] num){
int invIndex = findInvEle(num);
int nexInvToSwap = findNexInv(invIndex, num);
int[] nums = swap(invIndex, nexInvToSwap, num);
int[] merg = sort(nums, invIndex + 1, nums.length -1);
return merg;
}
//find number which smaller while traversing from left to right
private static int findInvEle(int[] num) {
int invInd = 0;
for(int i = num.length - 1; i >= 1; i--){
if(num[i -1] < num[i]){
invInd = i -1;
break;
}
}
return invInd;
}
//find the next least number after finding the above number and then swap
private static int findNexInv(int invInd,int[] num){
int nxtGrNow = -1;
int nxtGr = -1;
int nxtGrInd = -1;
for(int i = num.length - 1; i > invInd; i--){
if(num[invInd] < num[i]){
nxtGrNow = num[i];
if(nxtGr < nxtGrNow){
nxtGr = nxtGrNow;
nxtGrInd = i;
}
}
}
return invInd + nxtGrInd;
}
private static int[] swap(int invIndex,int nexInvToSwap, int[] num){
int temp = num[invIndex];
num[invIndex] = num[nexInvToSwap];
num[nexInvToSwap] = temp;
return num;
}
//sort all the elements after the inversion number found in the above method after swapping
@SuppressWarnings("null")
public static int[] sort(int[] nums,int invIndex ,int lastIndex){
if(nums.length == 0 || nums.length == 1)
return null;
int [] subArr = Arrays.copyOfRange(nums, invIndex, lastIndex + 1);
quickSort(subArr, 0, subArr.length - 1);
int[] mergerArr = new int[lastIndex + 1];
for(int i = 0; i < invIndex; i++){
mergerArr[i] = nums[i];
}
for(int i = 0; i <= subArr.length - 1; i++){
mergerArr[invIndex + i] = subArr[i];
}
return mergerArr;
}
public static void quickSort(int[] nums,int low ,int high){
int i = low;
int j = high;
int pivot = nums[(low + (high - low + 1))/2];
while(i <= j){
while(pivot > nums[i])
i++;
while(pivot < nums[j])
j--;
if(i <= j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++;
j--;
}
if(low < j)
quickSort(nums,low,j);
if(high > i)
quickSort(nums, i, high);
}
}
}
source: http://www.geeksforgeeks.org/find-next-greater-number-set-digits/
Comments
Post a Comment