Java 中打印数字中包含 1、2 和 3 的升序数字

2025年5月12日 | 阅读 5 分钟

目标是以升序打印包含数字 1、2 和 3 的数字数组，并用逗号分隔。如果没有包含数字 1、2 和 3 的数字，则打印 -1。

示例 1

输入： num_arr[] = {9821, 627183, 12, 1234}

输出1234, 627183

解释

9821 → 包含 1 和 2，但缺少 3。

627183 → 包含 1、2 和 3 → 包含

12 → 包含 1 和 2，但缺少 3 → 不包含

1234 → 包含 1、2 和 3 → 包含

示例 2

输入： num_arr[] = {456, 789, 321, 2134}

输出2134, 321

解释

456 → 缺少数字 1、2 和 3 → 不包含

789 → 缺少数字 1、2 和 3 → 不包含

包含 1、2 和 3 → 包含

2134 → 包含 1、2 和 3 → 包含

示例 3

输入： num_arr[] = {100, 150}

输出-1

解释

范围 [100, 150] 内的数字都不包含第一个、第二个和第三个数字。

方法：使用 Collections.sort() 方法

该软件使用 ArrayList 进行排序和动态存储，确保有效处理有效数字。它使用 String 操作 (contains()) 而不是数学运算来验证数字的存在，这使得验证更容易。

使用 Collections.sort() 可确保 O(N log N) 的排序复杂度。为了有效地连接字符串而不要求额外的内存分配，使用了 StringBuffer。该应用程序使用 O(N) 复杂度的迭代方法来扫描和过滤数字。

结合这些策略将确保完美实施和最佳性能。

算法

步骤 1：创建一个空的 ArrayList<Integer> 来存储包含 1、2 和 3 的数字。

步骤 2：调用 findOneTwoThree(n) 迭代 num_arr 中的每个整数 n，以确定 n 是否包含 1、2 和 3。

步骤 3：如果为 true，则将 n 添加到列表中。

步骤 4：使用 Collections.sort (arr) 对列表进行升序排序。

步骤 5：创建一个 StringBuffer 来存储格式化后的输出。

步骤 6：在遍历排序列表时，使用“,”分隔每个数字，并将其附加到 StringBuffer。

步骤 7：如果 StringBuffer 为空，则返回“ -1”，否则返回格式化字符串。

步骤 8：使用函数 Integer.toString(n) 将 n 转换为字符串 s。

步骤 9：利用 s.contains() 确定 s 是否包含“1”、“2”和“3”。

步骤 10：如果三个数字都存在，则返回 true；否则返回 false。

实施

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.io.FileNotFoundException;
public class NumbersAscendingOrder 
{
    private static String printNumbers(int[] num_arr)
    {
        // List to store numbers that contain 1, 2, and 3
        ArrayList<Integer> arr = new ArrayList<>();
        // Loop through the input array's numbers one by one.
        for (int n : num_arr) 
        {
            // Verify that the number includes the numbers 1, 2, and 3.
            if (findOneTwoThree(n))
            {
                arr.add(n); // Include the appropriate number in the list.
            }
        }
        // Sorting the list in the ascending order
        Collections.sort(arr);
        // The formatted output is stored in a StringBuffer.
        StringBuffer str_buffer = new StringBuffer();
        Iterator<Integer> it = arr.iterator();
        // Format the output after iterating through the sorted list.
        while (it.hasNext()) 
        {
            int val = it.next();
            if (str_buffer.length() > 0)
            {
                str_buffer.append(", "); // Append a comma separator
            }
            str_buffer.append(Integer.toString(val)); // Append the number
        }
        // If there were no valid numbers found, return "-1" or the formatted string.
        return (str_buffer.length() > 0) ? str_buffer.toString() : "-1";
    }
    // A method for determining whether an integer 
    // contains the numbers 1, 2, and 3
    private static boolean findOneTwoThree(int n)
    {
        String s = Integer.toString(n); 
        return (s.contains("1") && s.contains("2") && s.contains("3")); 
    }
    public static void main(String[] args)
    {
        int[] num_arr = { 456, 789, 321, 2134 };
        System.out.println(printNumbers(num_arr));
    }
}   

输出

 
321, 2134

复杂度分析

上述代码的时间复杂度为 O(N log(N))，其中 N 是给定数字的长度，空间复杂度为 O(N)。

方法：使用动态规划

为了优化重复检查，代码通过 HashMap 使用记忆化存储先前计算的结果。模 (%) 和除 (/) 运算用于有效提取数字。通过监控足够数字的存在，布尔标志 (has1, has2, has3) 减少了不必要的迭代。为了减少不必要的计算，动态规划 (DP) 通过在记忆化中缓存结果来实现。ArrayList 用于列表方法中的有效插入，它确保了有效数字的动态存储。为了提高执行速度并降低计算成本，使用条件检查来优化函数调用。

算法

步骤 1：创建一个记忆化 HashMap<Integer, Boolean> 来存储先前验证过的整数及其结果。

步骤 2：如果 n 存在于记忆化中，则返回存储的结果。

步骤 3：使用 has1 = false、has2 = false 和 has3 = false 初始化布尔标志。

步骤 4：使用除法 (/10) 和模数 (% 10) 从 n 中提取数字。

步骤 5：如果数字是 1，则设置 has1 = true；如果数字是 2，则设置 has2 = true；如果数字是 3，则设置 has3 = true。

步骤 6：持续提取数字，直到 n 等于 0。

步骤 7：在记忆化中存储结果（如果所有三个数字都已找到，则为 true；否则为 false）。

步骤 8：返回结果。

步骤 9：为了存储有效数字，初始化一个空列表 res。

步骤 10：对 num_arr 中的每个 n 重复执行此操作

步骤 10.1：逐个遍历 num_arr 中的每个 n：调用 contains123(n)。

步骤 10.2：然后，如果返回 true，则将 n 添加到 res 中。

步骤 11：返回 res。

实施

import java.util.*;
import java.io.*;
public class NumbersAscendingOrder 
{
    // Memoization map for integers that have been checked
    private static Map<Integer, Boolean> memoization = new HashMap<>();
    // A function that determines whether an integer
    // contains the numbers 1, 2, and 3.
    private static boolean contains123(int n) 
    {
        if (memoization.containsKey(n)) 
        {
            return memoization.get(n); // Return the stored result if it has already been calculated.
        }
        boolean has1 = false, has2 = false, has3 = false;
        int temp = n;
        while (temp > 0) 
        {
            int digit = temp % 10;
            if (digit == 1) has1 = true;
            if (digit == 2) has2 = true;
            if (digit == 3) has3 = true;
            temp /= 10;
        }
        boolean res = has1 && has2 && has3;
        memoization.put(n, res); // Store result in DP table
        return res;
    }
    // Function that returns numbers that contain 1, 2, and
    // 3 after processing an array
    public static List<Integer> printNumbers(int[] num_arr) {
        List<Integer> res = new ArrayList<>();
        for (int n : num_arr) 
        {
            if (contains123(n)) 
            {
                res.add(n);
            }
        }
        return res;
    }
    public static void main(String[] args) 
    {
        int[] num_arr = { 456, 789, 321, 2134 };
        System.out.println(printNumbers(num_arr));
    }
}   

输出

 
[321, 2134]

复杂度分析

上述代码的时间复杂度为 O(N log(M))，其中 N 是给定数字的长度，M 是 num_arr 中的最大数字。空间复杂度为 O(N)。

下一主题Java ASCII 表

Java 中打印数字中包含 1、2 和 3 的升序数字

方法：使用 Collections.sort() 方法

算法

实施

复杂度分析

方法：使用动态规划

实施

复杂度分析

联系信息

关注我们

教程

面试题

在线编译器

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 中打印数字中包含 1、2 和 3 的升序数字

方法：使用 Collections.sort() 方法

算法

实施

复杂度分析

方法：使用动态规划

实施

复杂度分析

相关帖子

Java 8 紧凑配置文件

Java 中计算二叉树的叶子节点

Java Architecture

Java 中的字符串压缩问题

JavaTuples 中的 KeyValue 类

Find Sum of the Series 0.6, 0.06, 0.006, 0.0006, …to n Terms in Java

Java 中使用多线程进行快速排序

System.out.println()

Autobiographical Number in Java

Java 中空类的大小

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器