Java 中的最长和谐子序列

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

给出了一个包含 n 个整数的数组。任务是找到数组的最长和谐子序列的大小。如果子序列中的最大值元素和最小值元素之间的差值为 1，则该子序列称为和谐子序列。

示例 1

输入

int inArr1[] = {11, 12, 12, 13, 14, 15, 11, 11, 11, 11}

输出

解释

最长的和谐子序列是 {11, 12, 12, 11, 11, 11, 11}，其大小为 7。因此，输出为 7。

示例 2

输入

int inArr1[] = {0, 1, 5, 8, 10, 19, 15, 25, 30, 40, 45, 7, 11}

输出

解释

最长的和谐子序列是 {0, 1} 或 {7, 8}，以及 {10, 11}。每个和谐子序列的大小为 2。因此，输出为 2。

蛮力法：使用位掩码

概念是利用位掩码技术生成所有可能的子序列。对于每个子序列，检查它是否是和谐子序列。找出所有可能的有效子序列中的最大长度。

观察以下步骤

步骤 1: 定义一个变量 ans。将其初始化为 0。变量 "ans" 将包含最终答案。

步骤 2: 迭代 'j' 从 0 到 '2^len - 1'，其中 'len' 是输入数组 'inputArr[]' 的长度。

初始化三个整数 'minVal'、'maxVal' 和 'currLen' 分别为 INT_MAX、INT_MIN 和 0，用于分别存储当前子序列的最小值、最大值和当前子序列的长度。
迭代 'k' 从 0 到 'len - 1'
- 如果 j 的 k^th 位被设置，并且 'MIN_VALUE' 小于 inputArr[k]，则更新 'MIN_VALUE' 为 inputArr[k]。
- 如果 j 的 k^th 位被设置，并且 'MAX_VALUE' 大于 inputArr[k]，则更新 'MAX_VALUE' 为 inputArr[k]。
- 增加 'currLen'，因为我们正在考虑子序列中的当前元素。
如果 'MIN_VALUE' 和 'MAX_VALUE' 之间的差值为 1，那么它是一个有效的子序列。因此，将 'ans' 更新为 'ans' 和 'currLen' 中的最大值。

步骤 3: 返回答案 'ans'。

现在，让我们观察上述算法的实现。

文件名: LongestHarmoniousSubsequence.java

public class LongestHarmoniousSubsequence
{
public static int lengthOfLHS(int[] inputArr, int len)
{
int ans = 0; // for storing the final answer

// Iterating from j = 0 to 2 ^ len - 1
for (int j = 0; j < (1l << len); j++)
{
    // Variables for storing the minimum, maximum values and 
    // the length of the subsequence, respectively

    int minVal = Integer.MAX_VALUE;
    int maxVal = Integer.MIN_VALUE;
    int currLen = 0;

    // Iterating over the input array array
    for (int k = 0; k < len; k++)
    {
        // If the kth bit of j is set
        if ((j & (1 << k)) != 0)
        {
            currLen = currLen + 1;
            minVal = Math.min(minVal, inputArr[k]);
            maxVal = Math.max(maxVal, inputArr[k]);
        }
    }

    // If the maximum difference is 1, then it is a harmonic subsequence
    // The rest of the other conditions are there to avoid overflow of Integer
    if (maxVal != Integer.MIN_VALUE && minVal != Integer.MAX_VALUE && maxVal - minVal == 1)
    {
        ans = Math.max(ans, currLen);
    }
}

// returning the final answer
return ans;
}


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

// input array
int inputArr[] = {11, 12, 12, 13, 14, 15, 11, 11, 11, 11};
int sze = inputArr.length; // computing size of the input array

System.out.println("For the input array: ");
for(int i = 0 ; i < sze; i++)
{
System.out.print(inputArr[i] + " ");
}
System.out.println( );
// invoking the method lengthOfLHS() for computing the 
// longest length of the Harmonic subsequence
int ans = obj.lengthOfLHS(inputArr, sze);

System.out.println("The length of the longest Harmonic subsequence is: " + ans);

System.out.println( "\n" );

// input array
int inputArr1[] = {0, 1, 5, 8, 10, 19, 15, 25, 30, 40, 45, 7, 11};
sze = inputArr1.length; // computing size of the input array

System.out.println("For the input array: ");
for(int i = 0 ; i < sze; i++)
{
System.out.print(inputArr1[i] + " ");
}
System.out.println( );

// invoking the method lengthOfLHS() for computing the 
// longest length of the Harmonic subsequence
ans = obj.lengthOfLHS(inputArr1, sze);
System.out.println("The length of the longest Harmonic subsequence is: " + ans);



}
}

输出

For the input array: 
11 12 12 13 14 15 11 11 11 11 
The length of the longest Harmonic subsequence is: 7


For the input array: 
0 1 5 8 10 19 15 25 30 40 45 7 11 
The length of the longest Harmonic subsequence is: 2

复杂度分析: 程序生成 0 到 2^len - 1 的所有二进制值。之后，程序遍历数组。因此，程序的整体时间复杂度为 O(len x 2^len)，其中 'len' 是输入数组的长度。此外，程序不使用额外的空间，因此空间复杂度为 O(1)。

程序的 time complexity 清楚地表明它不适用于较大的输入。因此，需要进行一些优化来降低 time complexity。

优化

概念是枢轴化数组的每个元素，然后只取那些相等或差值为 1 的元素，使得子序列中的最大差值为 1。

观察以下步骤。

步骤 1: 定义一个变量 ans。将其初始化为 0。变量 "ans" 将包含最终答案。

步骤 2: 迭代 'j' 从 0 到 'len - 1'

初始化 'currLen' 为 0。变量 'currLen' 用于保存当前子序列的长度。
定义一个布尔标志 'flg' 并将其赋值为 false，如果有可能构成和谐子序列，则该值为 true。
迭代 'k' 从 0 到 'len - 1'
- 如果 k^th 索引处的元素与 j^th 索引处的元素相同，则将 'currLen' 增加 1。
- 如果 k^th 索引处的元素比 j^th 索引处的元素大 1，则将 'currLen' 增加 1，并将标志 'flg' 设置为 true，因为当前子序列的最大差值为 1。
如果标志 'flg' 为 true，则将答案 'ans' 更新为 'ans' 和 'currLen' 中的最大值。

步骤 3: 返回 'ans' 作为最终答案。

现在，让我们观察上述算法的实现。

文件名: LongestHarmonioussubsequence1.java

public class LongestHarmoniousSubsequence1
{
public int lengthOfLHS(int[] inputArr, int len)
{
int ans = 0; // for storing the final answer

// Iterating over the array.
for (int j = 0; j < len; j++)
{
    boolean flg = false;
    int currLen = 0;

    // Iterating over the input array.
    for (int k = 0; k < len; k++)
    {
        // If the kth element of the array is 
        // the same as jth element of the array.
        if (inputArr[k] == inputArr[j])
        {
            currLen = currLen + 1;
        }
        
        // If kth element of the array is 1 larger than the jth element of 
        // the array, then it is the harmonic subsequence.
        if (inputArr[k] == 1 + inputArr[j])
        {
            currLen = currLen + 1;
            flg = true;
        }
    }
    
    // If it is a harmonic subsequence.
    if (flg)
    {
        ans = Math.max(ans, currLen);
    }
    
}

// returning the final answer
return ans;
}

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

// input array
int inputArr[] = {11, 12, 12, 13, 14, 15, 11, 11, 11, 11};
int sze = inputArr.length; // computing size of the input array

System.out.println("For the input array: ");
for(int i = 0 ; i < sze; i++)
{
System.out.print(inputArr[i] + " ");
}
System.out.println( );

// invoking the method lengthOfLHS() for computing the 
// longest length of the Harmonic subsequence
int ans = obj.lengthOfLHS(inputArr, sze);

System.out.println("The length of the longest Harmonic subsequence is: " + ans);

System.out.println( "\n" );

// input array
int inputArr1[] = {0, 1, 5, 8, 10, 19, 15, 25, 30, 40, 45, 7, 11};
sze = inputArr1.length; // computing size of the input array

System.out.println("For the input array: ");
for(int i = 0 ; i < sze; i++)
{
System.out.print(inputArr1[i] + " ");
}
System.out.println( );

// invoking the method lengthOfLHS() for computing the 
// longest length of the Harmonic subsequence
ans = obj.lengthOfLHS(inputArr1, sze);
System.out.println("The length of the longest Harmonic subsequence is: " + ans);



}
}

输出

For the input array: 
11 12 12 13 14 15 11 11 11 11 
The length of the longest Harmonic subsequence is: 7


For the input array: 
0 1 5 8 10 19 15 25 30 40 45 7 11 
The length of the longest Harmonic subsequence is: 2

复杂度分析: 在程序中，每个输入数组元素都会被枢轴化。此外，一个循环会遍历数组，需要 O(len) 的时间。因此，程序的整体时间复杂度为 O(len²)，其中 'len' 是输入数组的大小。程序的空间复杂度是常数，即 O(1)。

另一种方法：使用 HashMap

该方法是在 HashMap 中存储一个元素出现的次数。在每次迭代中，检查两件事

检查 inputArr[j] + 1 是否在 HashMap 中。如果存在，则当前子序列的长度将是 inputArr[j] 的总出现次数加上 (inputArr[j] + 1) 的总出现次数。
检查 inputArr[j] - 1 是否在 HashMap 中。如果存在，则当前子序列的长度将是 inputArr[j] 的出现次数加上 (inputArr[j] - 1) 的总出现次数。

步骤如下

步骤 1: 定义一个变量 ans。将其初始化为 0。变量 "ans" 将包含最终答案。

步骤 2: 定义一个 HashMap 'freqHashMap' 来存储输入数组 inputArr[] 中每个元素出现的次数。

步骤 3: 迭代 'j' 从 0 到 'len - 1'

在 HashMap 中增加 inputArr[j] 的计数。
如果 inputArr[j] + 1 存在于 HashMap 中，即 freqHashMap[inputArr[j] + 1] > 0，则将 'ans' 更新为 'ans' 和 (freqHashMap [inputArr[j]] + freqHashMap[inputArr[j] + 1]) 中的最大值。
如果 inputArr[j] - 1 存在于 HashMap 中，即 freqHashMap[inputArr[j] - 1] > 0，则将 'ans' 更新为 'ans' 和 (freqHashMap[inputArr[j]] + freqHashMap[inputArr[j] - 1]) 中的最大值。

步骤 4: 返回 'ans'。

以下程序实现了上述步骤。

文件名: LongestHarmonioussubsequence2.java

// importing HashMap and Map that are required
// in the program
import java.util.HashMap;
import java.util.Map;

public class LongestHarmonioussubsequence2
{
public int lengthOfLHS(int[] inputArr, int len)
{
int ans = 0; // for storing the final answer

// HashMap to store the count of every element.
Map<Integer, Integer> freqHashMap = new HashMap<Integer, Integer>();

// Iterating over the input array.
for (int j = 0; j < len; j++)
{
    // Incrementing the count of inputArr[j].
    int cnt = (freqHashMap.containsKey(inputArr[j])) ? freqHashMap.get(inputArr[j]) : 0;
    freqHashMap.put(inputArr[j], cnt + 1);

    
    //    If inputArr[j] + 1 is present, then it means it is possible to create a harmonic subsequence
    //    using all the occurrences of inputArr[j] and inputArr[j] + 1.
    
    if (freqHashMap.containsKey(inputArr[j] + 1))
    {
        ans = Math.max(ans, freqHashMap.get(inputArr[j]) + freqHashMap.get(inputArr[j] + 1));

    }

    // If inputArr[j] - 1 is present, then it means it is possible to make a harmonic subsequence
    // using all of the occurences of the inputArr[j] and inputArr[j] - 1.
    if (freqHashMap.containsKey(inputArr[j] - 1))
    {
        ans = Math.max(ans, freqHashMap.get(inputArr[j]) + freqHashMap.get(inputArr[j] - 1));
    }
}

return ans;
}

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

// input array
int inputArr[] = {11, 12, 12, 13, 14, 15, 11, 11, 11, 11};
int sze = inputArr.length; // computing size of the input array

System.out.println("For the input array: ");
for(int i = 0 ; i < sze; i++)
{
System.out.print(inputArr[i] + " ");
}
System.out.println( );
// invoking the method lengthOfLHS() for computing the 
// longest length of the Harmonic subsequence
int ans = obj.lengthOfLHS(inputArr, sze);

System.out.println("The length of the longest Harmonic subsequence is: " + ans);

System.out.println( "\n" );

// input array
int inputArr1[] = {0, 1, 5, 8, 10, 19, 15, 25, 30, 40, 45, 7, 11};
sze = inputArr1.length; // computing size of the input array

System.out.println("For the input array: ");
for(int i = 0 ; i < sze; i++)
{
System.out.print(inputArr1[i] + " ");
}
System.out.println( );

// invoking the method lengthOfLHS() for computing the 
// longest length of the Harmonic subsequence
ans = obj.lengthOfLHS(inputArr1, sze);
System.out.println("The length of the longest Harmonic subsequence is: " + ans);



}
}

输出

For the input array: 
11 12 12 13 14 15 11 11 11 11 
The length of the longest Harmonic subsequence is: 7


For the input array: 
0 1 5 8 10 19 15 25 30 40 45 7 11 
The length of the longest Harmonic subsequence is: 2

复杂度分析: 在程序中，使用一个循环遍历输入数组，并将每个元素的计数增加到 HashMap 中，其摊销时间复杂度为 O(1)。因此，程序的整体时间复杂度为 O(N)。此外，HashMap 最多可以增长到输入数组的大小。因此，程序的整体空间复杂度也为 O(N)。其中 N 是输入数组中的总元素数量。

下一个主题Java 中的 Count OR Pairs

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 全栈开发

Remove Loop in Linked List Using Java

Java 中将 JSON 转换为 Map

Java 中的集合与流

Java 中的流如何工作

Java 中的商业消费者问题

Java 中的旋转给定矩阵

Java 中的随遇多态

Java 中的四重数

Java 中的 @Deprecated 注解

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器