Java 中的漂亮数组

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

大小为 s 的数组被称为美丽数组，如果它满足以下三个条件

条件 1：数组的每个元素必须大于或等于 1 且小于或等于 s，即在 1 到 s（数组大小）之间。

条件 2：数组中不允许有重复的条目。

条件 3：数组的所有元素都不能按升序排列。

观察一些例子以便更好地理解。

示例 1

输入

inputArr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, size = 10

输出

否，给定的数组不是美丽的。

解释：尽管数组的所有元素都位于 1 到 size 的范围内，并且没有元素重复，但元素是按升序排列的。因此，违反了条件 3。因此，给定的数组不是美丽的。

示例 2

输入

inputArr[] = {1, 2, 3, 4, 5, 6, 7, 8, 19, 10}, size = 10

输出

否，给定的数组不是美丽的。

解释：元素 19 不在 1 到 size 的范围内。因此，条件 1 被违反。因此，给定的数组不是美丽的。

示例 3

输入

inputArr[] = {1, 2, 3, 4, 5, 6, 7, 9, 9, 10}, size = 10

输出

否，给定的数组不是美丽的。

解释：元素 9 重复。因此，条件 2 被违反。因此，给定的数组不是美丽的。

示例 4

输入

inputArr[] = {1, 2, 3, 4, 5, 6, 7, 8, 10, 9}, size = 10

输出

给定的数组是美丽的。

解释：数组的所有元素都位于 1 到 size 的范围内。因此，条件 1 得到满足。没有元素重复。因此，条件 2 得到满足。此外，数组的所有元素都不是按升序排列的。因此，条件 3 也得到满足。因此，所有提到的条件都得到满足，使得输入数组是美丽的。

方法/算法：使用排序

步骤 1：创建一个与输入数组大小相同的辅助数组。

步骤 2：使用循环将输入数组的所有元素复制到辅助数组中。复制时，还会检查数组的每个元素是否在 1 到 size s 的范围内。如果不在，则我们可以说输入数组不是美丽的。因此，无需进行步骤 3。如果每个元素都在范围内，则继续步骤 3。

步骤 3：对辅助数组进行排序。

步骤 4：使用循环，开始比较辅助数组的元素与输入数组的元素。在循环中，还要检查数组的元素是否唯一。

如果输入数组元素的排列与辅助数组元素的排列完全匹配，则表示元素按升序排列。因此，输入数组不是美丽的。
在有重复元素的情况下，数组不是唯一的。
如果元素既不是按升序排列，也没有重复元素，则我们可以说输入数组是美丽的。

实施

观察上述算法的实现。

文件名： BeautifulArray.java

// import statement for the Arrays
import java.util.Arrays;

public class BeautifulArray
{

// a method that checks whether the input array inputArr[]
// is beautiful or not
public boolean isBeautiful(int inputArr[])
{
    // computing the size of the inputArr array
    int size = inputArr.length;
    
    int auxArr[] = new int[size];
    
    for(int i = 0; i < size; i++)
    {
        // each element of the input array has to be within
        // the range 1 to size
        if(inputArr[i] >= 1 && inputArr[i] <= size)
        {
            // copying elements to the input array
            auxArr[i] = inputArr[i];
        }
        else
        {
            // if the control reaches here, then it means
            // there is at least one element in the input array 
            // that has gone out of the range. Hence, we can return false;
            return false;
        }
    }
    
    
    // sorting the auxiliary array
    Arrays.sort(auxArr);
    
    
    for(int i = 0; i < size; i++)
    {
        // checking whether the arrangement of the elements
        // in the input array matches with the auxArr or not
        if(inputArr[i] == auxArr[i])
        {
           if(i == size -  1)
           {
               // reaching here means the arrangement of each element of the input array
               // exactly matches with the arrangement of elements in the auxArr, i.e.,
               // elements are arranged in ascending order. Hence, we can return false.
               return false;
           }
        }
        
        // checking for repeated elements.
        if(i != 0 && auxArr[i] == auxArr[i - 1])
        {
            return false;
        }
    }
    
    // all the conditions are satisfied. Hence,
    // the input array is beautiful, and we can return true.
    return true;

}


// main method
public static void main(String argvs[])
{
    // input 1
    int inputArr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // creating an object of the class BeautifulArray
    BeautifulArray obj = new BeautifulArray();
    
    int s = inputArr.length;
    
    System.out.print("The following input array is: \n{ ");
    for(int i = 0; i < s; i++)
    {
        System.out.print(inputArr[i] + " ");
    }
    
    System.out.print("}");
    if(obj.isBeautiful(inputArr))
    {
        System.out.println(" is beautiful.");
    }
    else
    {
        System.out.println(" is not beautiful.");
    }
    
    System.out.println(" \n");
    
    // input 2
    int inputArr1[] = {1, 2, 3, 4, 5, 6, 7, 8, 19, 10};
    
    s = inputArr1.length;
    
    System.out.print("The following input array is: \n{ ");
    for(int i = 0; i < s; i++)
    {
        System.out.print(inputArr1[i] + " ");
    }
    
    System.out.print("}");
    if(obj.isBeautiful(inputArr1))
    {
        System.out.println(" is beautiful.");
    }
    else
    {
        System.out.println(" is not beautiful.");
    }
    
    System.out.println(" \n");
    
    
    // input 3
    int inputArr2[] = {1, 2, 3, 4, 5, 6, 7, 9, 9, 10};
    
    s = inputArr2.length;
    
    System.out.print("The following input array is: \n{ ");
    for(int i = 0; i < s; i++)
    {
        System.out.print(inputArr2[i] + " ");
    }
    
    System.out.print("}");
    if(obj.isBeautiful(inputArr2))
    {
        System.out.println(" is beautiful.");
    }
    else
    {
        System.out.println(" is not beautiful.");
    }
    
    System.out.println(" \n");
    
    
    // input 3
    int inputArr3[] = {1, 2, 3, 4, 5, 6, 7, 8, 10, 9};
    
    s = inputArr3.length;
    
    System.out.print("The following input array is: \n{ ");
    for(int i = 0; i < s; i++)
    {
        System.out.print(inputArr3[i] + " ");
    }
    
    System.out.print("}");
    if(obj.isBeautiful(inputArr3))
    {
        System.out.println(" is beautiful.");
    }
    else
    {
        System.out.println(" is not beautiful.");
    }
    
    
    
    
}

}

输出

The following input array is: 
{ 1 2 3 4 5 6 7 8 9 10 } is not beautiful.
 

The following input array is: 
{ 1 2 3 4 5 6 7 8 19 10 } is not beautiful.
 

The following input array is: 
{ 1 2 3 4 5 6 7 9 9 10 } is not beautiful.
 

The following input array is: 
{ 1 2 3 4 5 6 7 8 10 9 } is beautiful.

复杂度分析：由于排序，上述程序的 time complexity 为 O(n * log(n))。由于我们还使用了辅助数组，因此上述程序的 space complexity 为 O(n)，其中 n 是输入数组中存在的总元素数。

我们可以避免排序来降低 time complexity。观察以下方法。

方法：使用 HashMap

通过存储元素的出现频率，我们可以降低 time complexity。其算法如下。

步骤 1：创建一个哈希表。哈希表的键将是输入数组的元素，值将是元素出现的计数。

步骤 2：使用 for 循环，开始遍历输入数组的元素，并将其及其出现计数存储在哈希表中（在步骤 1 中创建）。在存储出现计数时，检查该元素的值是否在范围内。还要检查元素的排列以及任何元素的出现计数是否大于 1。

如果任何元素的出现计数大于 1，或者元素按升序排列，或者任何元素不在范围内，我们可以说输入数组不是美丽的；否则，是美丽的。

实施

文件名： BeautifulArray1.java

// import statement for the HashMap
import java.util.HashMap;

public class BeautifulArray1
{

// a method that checks whether the input array inputArr[]
// is beautiful or not
public boolean isBeautiful(int inputArr[])
{
    
    HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
    
    int size = inputArr.length;
    
    boolean isAscending = true;
    
    for(int i = 0; i < size; i++)
    {
        // each element of the input array has to be within
        // the range 1 to size
        if(inputArr[i] >= 1 && inputArr[i] <= size)
        {
            if(hm.containsKey(inputArr[i]))
            {   
                // we got an element atleast twice. 
                // Hence, the input array is not beautiful.
                return false;
            }
            else
            {
                hm.put(inputArr[i] , 1);
            }
            
        }
        
        else
        {
            // if the control reaches here, then it means
            // there is at least one element in the input array 
            // that has gone out of the range. Hence, we can return false;
            return false;
        }
        
        // checking whether the arrangement of the elements
        // in the input array is in the ascending order or not 
        if(i != 0 && inputArr[i] < inputArr[i - 1])
        {
           isAscending = false;
        }


    }
    
    if(!isAscending)
    {
        return true;
    }
    
    return false;
    
    
}


// main method
public static void main(String argvs[])
{
    // input 1
    int inputArr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // creating an object of the class BeautifulArray1
    BeautifulArray1 obj = new BeautifulArray1();
    
    int s = inputArr.length;
    
    System.out.print("The following input array is: \n{ ");
    for(int i = 0; i < s; i++)
    {
        System.out.print(inputArr[i] + " ");
    }
    
    System.out.print("}");
    if(obj.isBeautiful(inputArr))
    {
        System.out.println(" is beautiful.");
    }
    else
    {
        System.out.println(" is not beautiful.");
    }
    
    System.out.println(" \n");
    
    // input 2
    int inputArr1[] = {1, 2, 3, 4, 5, 6, 7, 8, 19, 10};
    
    s = inputArr1.length;
    
    System.out.print("The following input array is: \n{ ");
    for(int i = 0; i < s; i++)
    {
        System.out.print(inputArr1[i] + " ");
    }
    
    System.out.print("}");
    if(obj.isBeautiful(inputArr1))
    {
        System.out.println(" is beautiful.");
    }
    else
    {
        System.out.println(" is not beautiful.");
    }
    
    System.out.println(" \n");
    
    
    // input 3
    int inputArr2[] = {1, 2, 3, 4, 5, 6, 7, 9, 9, 10};
    
    s = inputArr2.length;
    
    System.out.print("The following input array is: \n{ ");
    for(int i = 0; i < s; i++)
    {
        System.out.print(inputArr2[i] + " ");
    }
    
    System.out.print("}");
    if(obj.isBeautiful(inputArr2))
    {
        System.out.println(" is beautiful.");
    }
    else
    {
        System.out.println(" is not beautiful.");
    }
    
    System.out.println(" \n");
    
    
    // input 3
    int inputArr3[] = {1, 2, 3, 4, 5, 6, 7, 8, 10, 9};
    
    s = inputArr3.length;
    
    System.out.print("The following input array is: \n{ ");
    for(int i = 0; i < s; i++)
    {
        System.out.print(inputArr3[i] + " ");
    }
    
    System.out.print("}");
    if(obj.isBeautiful(inputArr3))
    {
        System.out.println(" is beautiful.");
    }
    else
    {
        System.out.println(" is not beautiful.");
    }
    
    
    
    
}

}

输出

The following input array is: 
{ 1 2 3 4 5 6 7 8 9 10 } is not beautiful.
 

The following input array is: 
{ 1 2 3 4 5 6 7 8 19 10 } is not beautiful.
 

The following input array is: 
{ 1 2 3 4 5 6 7 9 9 10 } is not beautiful.
 

The following input array is: 
{ 1 2 3 4 5 6 7 8 10 9 } is beautiful.

复杂度分析：程序的 time complexity 为 O(n)，因为我们在单个循环中找到了输入数组的美丽度。此外，上述程序使用哈希表来存储元素及其频率。因此，space complexity 也为 O(n)，其中 n 是数组中存在的总元素数。

我们仍然可以在 space complexity 方面进行进一步优化。观察以下方法。

方法：使用 n 个自然数的和

我们可以利用给定的信息进行进一步优化。在问题中，已经给出，要使数组变得美丽，元素必须是 1 到 n（数组大小）之间的。因此，所有元素的总和必须等于前 n 个自然数的总和。如果总和过多或过少，则意味着某些元素要么不在范围内，要么某些元素重复。

int inputArr[] = {1, 2, 3, 4}; 这里 size = 4。因此，前 4 个自然数的总和为 (4 * (4 + 1)) / 2 = (4 * 5) / 2 = 20 / 2 = 10，这个 10 等于 1 + 2 + 3 + 4。如果我们从 inputArr[] 中取任何其他不在范围内的元素或重复任何元素，我们会得到一个不等于 10 的值。假设

inputArr[] = {1, 2, 3, 5}。这里，我们用了 5 而不是 4。因此，总和变为 1 + 2 + 3 + 5 = 11，不等于 10。如果我们取重复的元素，如下所示

inputArr[] = {1, 1, 3, 4}，这里我们两次取了 1 并消除了数字 2，我们得到 1 + 1 + 3 + 4 = 9，这再次不等于 10。

因此，我们看到，当数组元素的总和等于前 n 个自然数的总和时，它消除了元素超出范围以及元素重复的可能性。

然后唯一需要检查的是验证元素的排列是否按升序排列。下面的程序显示了这一点。

文件名： BeautifulArray2.java

public class BeautifulArray2
{

// a method that checks whether the input array inputArr[]
// is beautiful or not
public boolean isBeautiful(int inputArr[])
{
    int size = inputArr.length;
    
    int sumOfnNaturalNo = ((size * (size + 1))) / 2;
    
    boolean isAscending = true;
    
    int sumOfInputArrEle = 0;
    
    for(int i = 0; i < size; i++)
    {
        sumOfInputArrEle = sumOfInputArrEle + inputArr[i];
        
        // checking whether the arrangement of the elements
        // in the input array is in the ascending order or not 
        if(i != 0 && inputArr[i] < inputArr[i - 1])
        {
           isAscending = false;
        }


    }
    
    if(!isAscending && (sumOfInputArrEle == sumOfnNaturalNo))
    {
        return true;
    }
    
    return false;
    
    
}


// main method
public static void main(String argvs[])
{
    // input 1
    int inputArr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // creating an object of the class BeautifulArray2
    BeautifulArray2 obj = new BeautifulArray2();
    
    int s = inputArr.length;
    
    System.out.print("The following input array is: \n{ ");
    for(int i = 0; i < s; i++)
    {
        System.out.print(inputArr[i] + " ");
    }
    
    System.out.print("}");
    if(obj.isBeautiful(inputArr))
    {
        System.out.println(" is beautiful.");
    }
    else
    {
        System.out.println(" is not beautiful.");
    }
    
    System.out.println(" \n");
    
    // input 2
    int inputArr1[] = {1, 2, 3, 4, 5, 6, 7, 8, 19, 10};
    
    s = inputArr1.length;
    
    System.out.print("The following input array is: \n{ ");
    for(int i = 0; i < s; i++)
    {
        System.out.print(inputArr1[i] + " ");
    }
    
    System.out.print("}");
    if(obj.isBeautiful(inputArr1))
    {
        System.out.println(" is beautiful.");
    }
    else
    {
        System.out.println(" is not beautiful.");
    }
    
    System.out.println(" \n");
    
    
    // input 3
    int inputArr2[] = {1, 2, 3, 4, 5, 6, 7, 9, 9, 10};
    
    s = inputArr2.length;
    
    System.out.print("The following input array is: \n{ ");
    for(int i = 0; i < s; i++)
    {
        System.out.print(inputArr2[i] + " ");
    }
    
    System.out.print("}");
    if(obj.isBeautiful(inputArr2))
    {
        System.out.println(" is beautiful.");
    }
    else
    {
        System.out.println(" is not beautiful.");
    }
    
    System.out.println(" \n");
    
    
    // input 3
    int inputArr3[] = {1, 2, 3, 4, 5, 6, 7, 8, 10, 9};
    
    s = inputArr3.length;
    
    System.out.print("The following input array is: \n{ ");
    for(int i = 0; i < s; i++)
    {
        System.out.print(inputArr3[i] + " ");
    }
    
    System.out.print("}");
    if(obj.isBeautiful(inputArr3))
    {
        System.out.println(" is beautiful.");
    }
    else
    {
        System.out.println(" is not beautiful.");
    }
    
    
    
    
}

}

输出

The following input array is: 
{ 1 2 3 4 5 6 7 8 9 10 } is not beautiful.
 

The following input array is: 
{ 1 2 3 4 5 6 7 8 19 10 } is not beautiful.
 

The following input array is: 
{ 1 2 3 4 5 6 7 9 9 10 } is not beautiful.
 

The following input array is: 
{ 1 2 3 4 5 6 7 8 10 9 } is beautiful.

复杂度分析：程序的 time complexity 为 O(n)，因为我们在单个循环中找到了输入数组的美丽度，其中 n 是数组中存在的总元素数。上述程序没有使用任何额外空间来检查美丽数组。因此，程序的 space complexity 为 O(1)。

下一个主题Java 中的莫兰数

Java 中的漂亮数组

示例 1

示例 2

示例 3

示例 4

方法/算法：使用排序

实施

方法：使用 HashMap

实施

方法：使用 n 个自然数的和

联系信息

关注我们

教程

面试题

在线编译器

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

示例 4

方法/算法：使用排序

实施

方法：使用 HashMap

实施

方法：使用 n 个自然数的和

相关帖子

Duck Number Java

Find LCA in Binary Tree in Java

ArrayIndexOutOfBoundsException

Java Callable Example

Java 中容器和组件的区别

Make the String Lexicographically Larger in Java

Java 程序使用方法执行算术运算

Java 中将 Set 转换为 List

Java 中线段树的懒惰传播

Maximum difference of Zeros and Ones in Binary String Using Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器