Java Program to Check Whether an Array is a Permutation

2025年3月26日 | 阅读 8 分钟

数组排列

要确定数组 A 是否为排列，请确保它仅包含从 1 到 n 的每个数字一次，并且没有重复的元素。这证实了数组是一个完整且有效的序列。

数组排列示例

示例 1

输入： arr[] = {4, 1, 3, 2}

输出： 是

解释： 给定的数组是一个有效的排列，因为它包含了从 1 到 4 的所有数字。请注意，每个数字只出现一次。

示例 2

输入： arr[] = {1, 2, 3, 5, 5}

输出： 否

解释： 包含两个 5 的数组是无效的，因为它缺少数字 4，因此不是大小为 5 的有效排列。

解决问题的方法

蛮力搜索方法

该方法通过蛮力法检查从 1 到 n 的每个数字来验证数组是否为排列。嵌套循环导致时间复杂度为 O(n^2)，使其简单但不适用于大型数组。

算法

步骤 1： 一个大小为 size 的整数数组 array。

步骤 2： 从 1 到 size 迭代每个数字 num。

步骤 3： 对于每个 num，初始化一个布尔标志 isFound 为 false。迭代数组以检查 num 是否存在。

如果在数组中找到 num，则将 isFound 设置为 true 并跳出内层循环。
如果检查完所有元素都没有找到 num，则返回 false，表示数组不是排列。

步骤 4： 验证数组是否为排列。确保所有元素都在 1 和数组的大小或长度之间。

步骤 5： 如果是排列则打印“是”，否则打印“否”。

让我们在 Java 程序中实现上述方法。

文件名：PermutationCheck.java

import java.util.*; 
public class PermutationCheck { // Define the class
    // Function to check if an array includes all numbers from 1 to its size
    public static boolean checkPermutation(int[] array, int size) {
        // Iterate through numbers from 1 to size
        for (int num = 1; num <= size; num++) {
            boolean isFound = false; // defining a flag to determine if the current number is belongs to the array            
            // Check the array to determine if each number exists
            for (int index = 0; index < size; index++) {
                if (array[index] == num) {  // If the array element is found, Set the flag to true
                    isFound = true; 
                    break; // Exit the inner loop as the number is found
                }
            }
            // If the current number is not found in the array
            if (!isFound) {
                return false; // Return false, indicating the array is not a permutation
            }
        }
        return true; // If all numbers are found, return true, indicating the array is a permutation
    }
    // Main function to test the checkPermutation function
    public static void main(String[] args) {
        int[] array = { 4, 1, 3, 2 }; // defining an array
        int size = array.length; // finds the size of the array
        // Verify if the array is a permutation and display the outcome
        if (checkPermutation(array, size)) {
            System.out.println("Yes"); // Print "Yes" if it is a permutation
        } else {
            System.out.println("No"); // Print "No" if it is not a permutation
        }
    }
}   

输出

Yes

时间复杂度： 由于嵌套循环，时间复杂度为 O(n^2)。

辅助空间复杂度： 空间复杂度为 O(1)，因为只使用了少量额外变量。

使用 Set 数据结构

使用 Set 数据结构可以确保所有元素都是唯一的，并且可以高效地检查是否包含所有预期的元素。它会自动处理重复项，并提供快速的插入和查找操作，非常适合验证排列等任务。

算法

步骤 1： 初始化一个空的 Set 来存储数组中的唯一元素。

步骤 2： 将每个项添加到 Set 中，并记录看到的最高值。

步骤 3： 如果数组长度不等于最大值，则返回 false。

步骤 4： 检查 Set 的大小是否与数组的长度匹配。如果匹配，则每个元素都不同且在指定范围内。

步骤 5： 如果两个条件都满足，则给定数组是排列；否则不是排列。

让我们在 Java 程序中实现上述方法。

文件名：PermutationCheck.java

import java.util.*; 
class PermutationCheck {
    // Function to check if an array represents a permutation of numbers from 1 to length
    static boolean isPermutation(int[] array, int length) {
        Set<Integer> uniqueElements = new HashSet<Integer>(); // Set to store unique elements from the array
        int maximumElement = 0; // Variable to keep track of the maximum element in the array
        // Loop iterate over each element in the array
        for (int i = 0; i < length; i++) {
            uniqueElements.add(array[i]); // Add the current array element to a set
            maximumElement = Math.max(maximumElement, array[i]); // Update the maximum element if current element is greater
        }
        // Check if the maximum element is equal to the length of the array
        if (maximumElement != length)
            return false; // Return false if the maximum element is not equal to length, indicating the array is not a permutation
        // Check if the size of the set is equal to the length of the array
        if (uniqueElements.size() == length)
            return true; // Return true if the size of the set equals length, indicating the array is a permutation
        return false; // Return false if not all conditions are met
    }
    // Main function to test the isPermutation function
    public static void main(String[] args) {
        int[] array = { 4, 1, 3, 2 }; // Initialize the array 
        int length = array.length; // finds the length of the array
        // Check if the array is a permutation and print the result
        if (isPermutation(array, length))
            System.out.println("Yes"); // if the array is a permutation, print yes
        else
            System.out.println("No"); // if the array is not a permutation, print no
    }
}   

输出

Yes

时间复杂度： O(N log N)，因为将 N 个元素插入 Set。

辅助空间： O(N)，用于在 Set 中存储多达 N 个唯一元素。

使用排序和比较的方法

排序和比较方法首先按升序对数组进行排序。然后检查每个元素是否与其预期值匹配，从而确认数组正好包含从 1 到大小的所有整数。

算法

步骤 1： 将数组按递增顺序排列。

步骤 2： 遍历已排序数组中的每个项。

步骤 3： 检查索引 i 处的每个元素是否等于 i + 1。如果不等于，则返回 false。

步骤 4： 如果所有元素都与其预期值匹配，则返回 true，表示数组是排列。

步骤 5： 完成函数并根据检查输出结果。

让我们在 Java 程序中实现上述方法。

文件名：PermutationCheck.java

import java.util.*; 
class PermutationCheck {
    // Function to check if an array represents a permutation of numbers from 1 to size
    static boolean isPermutation(int[] array, int size) {
        Arrays.sort(array); // Sort the array to arrange elements in ascending order
        // Traverse through the sorted array
        for (int i = 0; i < size; i++) {
            // Check the current array element with its expected value (i + 1)
            if (array[i] != i + 1) return false; // Return false if the current element does not match its expected value
        }
        return true; // Return true if all elements are as expected, indicating the array is a permutation
    }
    // Main function to test the isPermutation function
    public static void main(String[] args) {
        int[] array = {4, 1, 3, 2}; // Initialize the array 
        int size = array.length; // finds the length of the array
        // printing the results
        if (isPermutation(array, size))
            System.out.println("Yes"); // if the array is a permutation, print yes
        else
            System.out.println("No"); // if the array is not a permutation, print no
        return; // End of the main function
    }
}   

输出

Yes

时间复杂度： O(N log N)，由于排序操作。

辅助空间： O(1)，因为排序是就地完成的。

使用布尔数组跟踪访问的方法

该方法使用一个布尔数组来跟踪访问过的元素，确保从 1 到 N 的每个数字恰好出现一次。如果数字重复或超出预期范围，则返回 false。否则，它会确认数组是排列。

算法

步骤 1： 定义一个大小与原始数组相同的布尔数组，并将其所有元素初始化为 false。该数组跟踪已看到的数字。

步骤 2： 对于输入数组中的每个元素

检查 seen 数组中相应的索引是否为 false。如果为 false，则将其设置为 true，表示该数字已被看到。
如果 seen 数组中相应的索引已为 true，则立即返回 false，因为这表示有重复项，意味着该数组不是有效的排列。

步骤 3： 遍历完输入数组后，检查 seen 数组以确保从 1 到 length 的所有元素都存在。

步骤 4： 检查 seen 数组中是否有任何值仍然为 false。如果是，则返回 false，因为该数组不是有效的排列。

步骤 5： 如果所有值都为 true 且没有重复项，则返回 true，表示该数组是有效的排列。

让我们在 Java 程序中实现上述方法。

文件名：PermutationChecker.java

import java.util.Arrays; 
public class PermutationChecker {
    // function to check if an array contains a unique set of numbers from 1 to the length of the array
    public static boolean isPermutation(int[] array, int length) {
        boolean[] seen = new boolean[length]; // Utilize a boolean array for monitoring the numbers that have been observed
        Arrays.fill(seen, false); // Set all elements in the boolean array to be false initially
        // Iterate through the input array
        for (int i = 0; i < length; i++) {
            // Verify whether the number present in array[i] has not been encountered before
            if (!seen[array[i] - 1]) {
                seen[array[i] - 1] = true; // Mark the number as seen
            } else {
                return false; // Return false if the number has already been seen, indicating a duplicate
            }
        }
        // ensure that all numbers from 1 to the size of the array have been checked
        for (int i = 0; i < length; i++) {
            if (!seen[i]) {
                return false; // Return false if any number from 1 to length is missing
            }
        }
        return true; // Return true if all numbers are present and there are no duplicates
    }
    // Main function to test the isPermutation function
    public static void main(String[] args) {
        int[] array = { 3, 1, 4, 2 }; // Initialize the array by inputting test data
        int length = array.length; // Get the length of the array.
        // Verify if the array is a permutation and display the outcome
        if (isPermutation(array, length)) {
            System.out.println("YES"); // Print "YES" if the array is a valid permutation
        } else {
            System.out.println("NO"); // Display "NO" if the array does not constitute a valid permutation
        }
    }
}   

输出

YES

时间复杂度： 代码遍历数组两次。因此，时间复杂度为 O(N)，这直接与元素数量相关。

辅助空间： 代码使用大小为 N 的布尔数组来跟踪已看到的数字。需要 O(N) 的额外空间。

下一个主题Java-program-to-compute-the-number-of-integers-divisible-by-k-in-the-range-a-b

Java Program to Check Whether an Array is a Permutation

数组排列

数组排列示例

解决问题的方法

蛮力搜索方法

使用 Set 数据结构

使用排序和比较的方法

使用布尔数组跟踪访问的方法

联系信息

关注我们

教程

面试题

在线编译器

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 Program to Check Whether an Array is a Permutation

数组排列

数组排列示例

解决问题的方法

蛮力搜索方法

使用 Set 数据结构

使用排序和比较的方法

使用布尔数组跟踪访问的方法

相关帖子

Java 中 CyclicBarrier 和 CountDownLatch 的区别

Java 中的 getSource() 方法

Java 中将 Set 转换为 Array

Java 中的语音处理

Java API

Java case keyword

Java 中的 2048 游戏

Unary Operators in Java

NumberSolitaire Problem in Java

Java 中 Iterator 和 ListIterator 的区别及示例

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器