Java 中具有相同数字集的下一个更大的数字

2024年9月10日 | 阅读 9 分钟

给出一个数字 (num)。任务是找到一个由 num 的数字组成且大于 num 的最小数字。如果数字 num 是其数字集中可能的最大数字，则无法找到下一个更大的数字，因此应显示相应消息。

示例 1

输入 89321

输出 91238

解释：由数字 1、2、3、8、9 组成的、大于数字 89123 的数字是

98123, 98132, 98213, 98231, 98312, 98321, 93128, 93182, 93218, 93281, 93812, 93821, 92138, 92183, 92318, 92381, 92813, 92831, 91238, 91283, 91328, 91382, 91823, 91832

在所有这些数字中，最小的数字是 91238。

示例 2

输入 3648

输出 3684

解释：由数字 3、8、4、6 组成的、大于 3648 的数字是

3684, 4368, 4386, 4638, 4683, 4836, 4863, 6348, 6384, 6438, 6483, 6834, 6843, 8346, 8364, 8436, 8463, 8634, 8643

在所有这些数字中，最小的数字是 3684。

示例 3

输入 9100

输出：无法找到下一个更大的数字。

解释：由数字 9、1、0、0 组成的最大数字是 9100。因此，无法使用给定的数字找到大于 9100 的数字。

观察

以下是一些重要的观察点。

如果数字的数字按降序排列，则结果是“无法找到下一个更大的数字”。例如，98675。
如果数字的数字按升序排列，则需要交换数字的最后两位数字。例如，对于数字 4567，下一个更大的数字是 4576。
对于其他所有情况，需要从最右边的数字开始处理，因为需要找到大于给定数字的数字中的最小者。

算法

以下是基于上述观察计算下一个更大数字的算法。

步骤 1：从最右边的数字开始遍历数字 num，继续遍历直到找到一个小于最后一个遍历数字的数字。例如，如果输入数字为“4975”，则必须在 4 处停止。这是因为 4 小于下一个数字 9。如果找不到这样的数字，则无法找到下一个更大的数字。

步骤 2：现在，在上述找到的数字 'd' 的右侧搜索大于 'd' 的最小数字。对于数字 4975，4 的右侧包含 975。在数字 9、7 和 5 中，大于 4 的最小数字是 5。

步骤 3：现在，交换数字 4 和 5。这样，您将得到 5974。但是，这个数字不是最大的数字中最小的。因此，我们需要对数字 5 之后的数字进行排序。因此，通过对数字 5*974* 的数字进行排序，您将得到 5*479*。数字 5479 是大于数字 4975 且由数字 4、9、7、5 组成的数字中最小的。

使用排列

这是一种蛮力方法。在此方法中，我们将计算使用给定数字 num 中的数字可以形成的每个数字。我们将这些计算出的数字存储在哈希集 *hs* 中。在该哈希集中，我们将选择一个最小的且大于数字 num 的数字。

文件名： NextGreaterNumber.java

// important import statements
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class NextGreaterNumber
{


public Set<Integer> hs;

// constructor of the class
NextGreaterNumber()
{
hs = new HashSet();
}

// a method that finds the next greater number
int findNextGreaterNum(int num)
{

int n = num;    
ArrayList<Integer> al = new ArrayList<Integer>();

// loop for extracting the digits of the number num
// and adding those digits to the array list in the reverse order
while(n != 0)
{
al.add(n % 10);
n = n / 10;
}

// permute to find all the numbers using the digits
// stored in the array list
permute(al, 0, al.size() - 1);

int ans = findMin(hs, num);

return ans;


}

// a method that finds the minimum from the set s
// that minimum should be greater than num
public int findMin(Set<Integer> s, int num)
{
int min = Integer.MAX_VALUE;


// making an integer array using the set S
Integer[] intArr = s.toArray(new Integer[s.size()]);


// size of the array
int size = intArr.length;

// the value of this flag will be true
// when a valid minimum is found
boolean flag = false;

for(int i = 0 ; i < size; i++)
{
int temp = intArr[i];

// the value we are going to find
// has to more than the number num
if(temp > num)
{
//  among the greater value we have to 
// pick the minimum
if(min > temp)
{
min = temp;

// minimum found!
// hence update the value of the  
// boolean flag
flag = true;
}
}

}


// if the value of flag is true
// return the minimum value
if(flag)
{
return min;
}


// if the control reaches here then it means 
// the minimum value is not found. Therefore, return 
// -1
return -1;
}


// swap the value in the array list al at the positions 
// x & y
public void swap(ArrayList<Integer> al, int x, int y)
{
int i = al.get(x);
int j = al.get(y);

al.set(x, j);
al.set(y, i);
}

// using the digits present in the array list 
// create a number. Note that the digits in the num 
//  has the same order that is there in the array list
// For example, al = [2, 3, 6, 1, 1, 9, 8], then the number formed
// will be 2361198
int composeNum(ArrayList<Integer> al)
{
int size = al.size();
int num = 0;

for(int i = 0; i < size; i++)
{
num = num * 10;
num = num + al.get(i);
}

return num;

}


// a method that finds out the numbers that can be composed
// using the digits present in the array list al
private void permute(ArrayList<Integer> al, int l, int r)
{
// handling the base case
if (l == r)
{
// compose the number using the digits present 
// in the array list and add it to the hash set
int num = composeNum(al);
hs.add(num);
}

else
{
for (int j = l; j <= r; j++)
{
// swap then apply recursion and then 
// again swap in order to backtrack
swap(al, l, j);
permute(al, l + 1, r);
swap(al, l, j);
}
}
}


// main method
public static void main(String[] argvs)
{
// creating an object of the class NextGreaterNumber
NextGreaterNumber obj = new NextGreaterNumber();

// input 1
int num = 536479;

int ans = obj.findNextGreaterNum(num);

System.out.println("For the number: " + num);

if(ans != -1)
{
System.out.println("The next greater number is: " + ans);
}
else
{
System.out.println("The next greater number is not possible.");    
}

System.out.println();

obj.hs.clear();

// input 2
num = 654321;

ans = obj.findNextGreaterNum(num);

System.out.println("For the number: " + num);

if(ans != -1)
{
System.out.println("The next greater number is: " + ans);
}
else
{
System.out.println("The next greater number is not possible.");    
}


System.out.println();

obj.hs.clear();

// input 3
num = 4876;

ans = obj.findNextGreaterNum(num);

System.out.println("For the number: " + num);

if(ans != -1)
{
System.out.println("The next greater number is: " + ans);
}
else
{
System.out.println("The next greater number is not possible.");    
}


}
}

输出

For the number: 536479
The next greater number is: 536497

For the number: 654321
The next greater number is not possible.

For the number: 4876
The next greater number is: 6478

复杂度分析：在上面的程序中，我们使用了回溯来查找下一个更大的数字。因此，该程序的时间复杂度是指数级的。假设数字 num 有 d 位数字。因此，哈希集 hs 中的总数字数为 n!。因此，该程序空间复杂度为 O(n!)。

使用排序

文件名： NextGreaterNumber

// important import statements
import java.util.ArrayList;
import java.util.Collections;

public class NextGreaterNumber
{
boolean isSwapPossible(ArrayList<Integer> al)
{
int size = al.size();
int j;

// loop for traversing from right to left
for (j = size - 1; j > 0; j--)
{
int x = al.get(j);
int y = al.get(j - 1);


if (x > y) 
{
// we have got a digit that is 
// less than the next digit
// hence the processing starts right here
break;
}
}


if(j == 0)
{
// all digits of the numbers
// are arranged in descending order. Hence, the next greater number
// is not possible
return false;
}

int a = al.get(j - 1);
int min = j;

// Finding a digit that is greater than the digit
// located at (j - 1)th index. However, among the collection of the
// greater digits we have to pick the smallest
for (int k = j + 1; k < size; k++)
{
if (al.get(k) > a && al.get(k) < al.get(min))
{
min = k;
}
}

// swapping to get the greater number
int x = al.get(j - 1);
int y = al.get(min);
al.set(min, x);
al.set(j - 1, y);


// sorting for getting the smallest among the numbers 
//  that are larger than num
Collections.sort(al.subList(j, size));

return true;

}

// a method that finds the next greater number
int findNextGreaterNum(int num)
{

int n = num;    
ArrayList<Integer> al = new ArrayList<Integer>();

// loop for extracting the digits of the number num
// and adding those digits to the array list in the reverse order
while(n != 0)
{
al.add(n % 10);
n = n / 10;
}

// reversing the order of digits so that the current order is maintained
Collections.reverse(al);

// if the swap is possible, then return
// the next greater number
if(isSwapPossible(al))
{
int newNum = 0;
int size = al.size();

// loop for combining the digits present 
// in the list to create a new number, which is next greater 
// number number
for (int j = 0; j < size; j++)
{
newNum = newNum * 10;
newNum = newNum + al.get(j);
}

// returning the new greater number
return newNum;
}



// if the control reaches here, then it means the next greater number is not 
// possible. Hence, -1 is returned
return -1;
}


// main method
public static void main(String[] argvs)
{
// creating an object of the class NextGreaterNumber
NextGreaterNumber obj = new NextGreaterNumber();

// input 1
int num = 536479;

int ans = obj.findNextGreaterNum(num);

System.out.println("For the number: " + num);

if(ans != -1)
{
System.out.println("The next greater number is: " + ans);
}
else
{
System.out.println("The next greater number is not possible.");    
}

System.out.println();

// input 2
num = 654321;

ans = obj.findNextGreaterNum(num);

System.out.println("For the number: " + num);

if(ans != -1)
{
System.out.println("The next greater number is: " + ans);
}
else
{
System.out.println("The next greater number is not possible.");    
}


System.out.println();


// input 3
num = 4876;

ans = obj.findNextGreaterNum(num);

System.out.println("For the number: " + num);

if(ans != -1)
{
System.out.println("The next greater number is: " + ans);
}
else
{
System.out.println("The next greater number is not possible.");    
}


}
}

输出

For the number: 536479
The next greater number is: 536497

For the number: 654321
The next greater number is not possible.

For the number: 4876
The next greater number is: 6478

复杂度分析：在上面的程序中，我们使用了循环和排序。循环需要 O(n) 时间，排序需要 O(n * log(n)) 时间。因此，程序总时间复杂度为 O(n + n * log(n))，其中 n 是输入数字中总位数。由于没有使用额外的空间；因此，程序空间复杂度是常数，即 O(1)。

注意：我们甚至可以进一步降低时间复杂度。请注意，除了排序之外，我们还可以使用内置的反转方法进行排序。这是因为我们正在排序的数字按降序排列。例如，排序 6、5、4、3、2、1 不应花费 O(n x log(n)) 时间。只需反转顺序即可完成工作。因此，除了排序之外，使用 reverse() 方法可将时间复杂度降低到 O(n)。

在 isSwapPossible() 方法中，进行以下更改以获得相同的结果。

    boolean isSwapPossible(ArrayList<Integer> al)
    {
          // same code as the mentioned in the above program for this method            
           // comment out the Collections.sort() and add Collections.reverse() method 
           // Collections.sort(al.subList(j, size));
            
           // reverse the digits to find the next greater number
          Collections.reverse(al.subList(j, size));
          
     

        return true;
        
    }

下一个主题Java 中将数字字符串拆分为素数

← 上一个下一个 →

Java 中具有相同数字集的下一个更大的数字

观察

算法

使用排列

使用排序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中具有相同数字集的下一个更大的数字

观察

算法

使用排列

使用排序

相关帖子

Java 中比较两个 Excel 文件

Java 中查找 N 个二进制字符串中的第 K 位

How to Create Test Cases for Exceptions in Java

Java 中 ToIntFunction 接口及示例

How to Generate Random Number in Java

Java Tokens

Design Principles in Java

DoubleBuffer reset() methods in Java with Examples

如何在 Java 中计算两个日期之间的时间差

Java ByteBuffer 大小

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器