长度不超过1的两个不同值的最长子数组

Question

长度不超过1的两个不同值的最长子数组

javaalgorithm

6

给定一个整数数组，最长的子数组长度是多少，其中包含不超过两个不同的值，这些不同的值之间的差异不超过1。

例如：

arr = [0, 1, 2, 1, 2, 3] -> 长度为4; [1,2,1,2]

arr = [1, 2, 3, 4, 5] -> 长度为2; [1,2]

arr = [1, 1, 1, 3, 3, 2, 2] -> 长度为4; [3,3,2,2]

我有这样的代码

 public static int longestSubarray(List<Integer> arr) {
        int max = 0;
        Set<Integer> set = new HashSet<>();
        int i = 0;
        int j = 1;
        while (i < arr.size() - 1) {
            set.add(arr.get(i));
            while (j < arr.size() && Math.abs(arr.get(i) - arr.get(j)) < 2) {
                if (!set.contains(arr.get(j))) {
                    if (set.size() == 2) {
                        break;
                    } else {
                        set.add(arr.get(j));
                    }
                }
                ++j;
            }
            max = Math.max(max, j - i);
            j = ++i + 1;
            set.clear();
        }
        return max;
    }

有更好的解决方案吗？

- Igor Pereverzev

在测试用例 [1, 295331535] 的情况下，输出将为 0，但预期结果是 1。 - Mohamed AbdElRazek

4个回答

4

C#代码：

using System.IO;
using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<int> arr = new List<int>(){ 0, 1, 2, 1, 2, 3};
        List<int> set = new List<int>(); 
        int n = arr.Count;
        int max = 1;
        int i,j;
        for(i=0 ; i<n-1; i++)
        {
            set.Add(arr[i]);
            for(j=i+1; j<n; )
            {
                if(Math.Abs(arr[i]-arr[j])<2)
                {
                    if(!set.Contains(arr[j]))
                    {
                        if(set.Count == 2)
                        break;
                        else
                        set.Add(arr[j]);
                    }  
                }
                else
                break;
            j++;
            }
            max = Math.Max(max,j-i);
            set.Clear();
        }
        Console.WriteLine(max); 
    }
}

- Sarvesh Singh

我正在寻找解决这个问题的方法，参考了您的代码并在C#中实现了相同的功能。谢谢！ - Sarvesh Singh

你能解释一下为什么要使用List<int>集合吗？我特别不理解为什么在set.Count达到2时要中断。 - Tiamo Idzenga

1

参考这篇GFG文章，然后将X替换为1

链接: https://www.geeksforgeeks.org/longest-subarray-in-which-absolute-difference-between-any-two-element-is-not-greater-than-x/

- VR7

欢迎提供解决方案的链接，但请确保您的答案即使没有链接也是有用的：在链接周围添加上下文，以便其他用户了解它的内容和原因，然后引用您链接的页面中最相关的部分，以防目标页面不可用。仅仅提供链接的答案可能会被删除。 - Yunnosch

-3

具有O(n)时间复杂度的Java解决方案

static int solution(List arr) {

    int subArrStart = 0;
    int changedSubArrStart = 0;

    int longSubArrayLen = 0;
    int currSubArrayLen = 0;

    for (int i = 0; i < arr.size(); i++) {

        if (arr.get(subArrStart) == arr.get(i)) {
            currSubArrayLen++;
        } else if (Math.abs(arr.get(subArrStart) - arr.get(i)) == 1) {
            if (subArrStart == changedSubArrStart) {
                changedSubArrStart = i;
            }
            currSubArrayLen++;
        } else if (Math.abs(arr.get(changedSubArrStart) - arr.get(i)) == 1) {
            subArrStart = changedSubArrStart;
            currSubArrayLen = i - subArrStart + 1;
        } else {
            subArrStart = i;
            changedSubArrStart = i;
            currSubArrayLen = 1;
        }

        longSubArrayLen = Math.max(longSubArrayLen, currSubArrayLen);
    }
    return longSubArrayLen;
}

- Kovalan V

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- גלעד ברקן · Accepted Answer

是的。这里有一个时间复杂度为 O(n) ，空间复杂度为 O(1) 的动态规划程序。其思想是，我们可以通过查看可能包含更高元素的以 A[i-1] 结尾的最佳序列和可能包含更低元素的以 A[i-1] 结尾的最佳序列来获得以 A[i] 结尾的序列的答案。

JavaScript 代码：

function f(A){
  if (A.length < 2)
    return A.length;
    
  let best = 1;
  let bestLower = 1;
  let bestHigher = 1;
  
  for (let i=1; i<A.length; i++){
    if (A[i] == A[i-1]){
      bestLower = bestLower + 1;
      bestHigher = bestHigher + 1;
    
    } else if (A[i] - 1 == A[i-1]){
      bestLower = 1 + bestHigher;
      bestHigher = 1;
    
    } else if (A[i] + 1 == A[i-1]){
      bestHigher = 1 + bestLower;
      bestLower = 1;
    
    } else {
      bestLower = 1;
      bestHigher = 1;
    }

    best = Math.max(best, bestLower, bestHigher);
  }
  
  return best;
}

arrays = [
  [0, 1, 2, 1, 2, 3], // length = 4; [1,2,1,2]
  [1, 2, 3, 4, 5], // length = 2; [1,2]
  [1, 1, 1, 3, 3, 2, 2] // length = 4; [3,3,2,2]
];

for (let arr of arrays){
  console.log(JSON.stringify(arr));
  console.log(f(arr));
}