最长子数组，其中不超过两个不同值，这些值之间的差异不超过1。

huangapple
go评论119阅读模式
英文:

Longest subArray with no more than two distinct values that differ by no more than 1

问题

给定一个整数数组，要求找出包含不超过两个不同值的最长子数组的长度，使得这两个不同的值的差值不超过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]

我有以下代码：

  1. public static int longestSubarray(List<Integer> arr) {
  2.     int max = 0;
  3.     Set<Integer> set = new HashSet<>();
  4.     int i = 0;
  5.     int j = 1;
  6.     while (i < arr.size() - 1) {
  7.         set.add(arr.get(i));
  8.         while (j < arr.size() && Math.abs(arr.get(i) - arr.get(j)) < 2) {
  9.             if (!set.contains(arr.get(j))) {
  10.                 if (set.size() == 2) {
  11.                     break;
  12.                 } else {
  13.                     set.add(arr.get(j));
  14.                 }
  15.             }
  16.             ++j;
  17.         }
  18.         max = Math.max(max, j - i);
  19.         j = ++i + 1;
  20.         set.clear();
  21.     }
  22.     return max;
  23. }

是否有更好的解决方案？

英文:

Given an array of integers what is the length of the longest subArray containing no more than two distinct values such that the distinct values differ by no more than 1

For Example:

arr = [0, 1, 2, 1, 2, 3] -> length = 4; [1,2,1,2]

arr = [1, 2, 3, 4, 5] -> length = 2; [1,2]

arr = [1, 1, 1, 3, 3, 2, 2] -> length = 4; [3,3,2,2]

I have such code

  1.  public static int longestSubarray(List&lt;Integer&gt; arr) {
  2.         int max = 0;
  3.         Set&lt;Integer&gt; set = new HashSet&lt;&gt;();
  4.         int i = 0;
  5.         int j = 1;
  6.         while (i &lt; arr.size() - 1) {
  7.             set.add(arr.get(i));
  8.             while (j &lt; arr.size() &amp;&amp; Math.abs(arr.get(i) - arr.get(j)) &lt; 2) {
  9.                 if (!set.contains(arr.get(j))) {
  10.                     if (set.size() == 2) {
  11.                         break;
  12.                     } else {
  13.                         set.add(arr.get(j));
  14.                     }
  15.                 }
  16.                 ++j;
  17.             }
  18.             max = Math.max(max, j - i);
  19.             j = ++i + 1;
  20.             set.clear();
  21.         }
  22.         return max;
  23.     }

Can there be a better solution?

答案1

得分: 6

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

JavaScript代码：

  1. function f(A){
  2.   if (A.length < 2)
  3.     return A.length;
  4.     
  5.   let best = 1;
  6.   let bestLower = 1;
  7.   let bestHigher = 1;
  8.   
  9.   for (let i=1; i<A.length; i++){
  10.     if (A[i] == A[i-1]){
  11.       bestLower = bestLower + 1;
  12.       bestHigher = bestHigher + 1;
  13.     
  14.     } else if (A[i] - 1 == A[i-1]){
  15.       bestLower = 1 + bestHigher;
  16.       bestHigher = 1;
  17.     
  18.     } else if (A[i] + 1 == A[i-1]){
  19.       bestHigher = 1 + bestLower;
  20.       bestLower = 1;
  21.     
  22.     } else {
  23.       bestLower = 1;
  24.       bestHigher = 1;
  25.     }
  27.     best = Math.max(best, bestLower, bestHigher);
  28.   }
  29.   
  30.   return best;
  31. }
  33. arrays = [
  34.   [0, 1, 2, 1, 2, 3], // 长度为 4; [1,2,1,2]
  35.   [1, 2, 3, 4, 5],    // 长度为 2; [1,2]
  36.   [1, 1, 1, 3, 3, 2, 2] // 长度为 4; [3,3,2,2]
  37. ];
  39. for (let arr of arrays){
  40.   console.log(JSON.stringify(arr));
  41.   console.log(f(arr));
  42. }
英文:

Yes. Here's a dynamic program with O(n) time and O(1) space. The idea is that we can get the answer for the sequence ending at A[i] by looking at the best sequence ending at A[i-1] that possibly included higher elements, and the best sequence ending at A[i-1] that possibly included lower elements.

JavaScript code:

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

  1. function f(A){
  2.   if (A.length &lt; 2)
  3.     return A.length;
  4.     
  5.   let best = 1;
  6.   let bestLower = 1;
  7.   let bestHigher = 1;
  8.   
  9.   for (let i=1; i&lt;A.length; i++){
  10.     if (A[i] == A[i-1]){
  11.       bestLower = bestLower + 1;
  12.       bestHigher = bestHigher + 1;
  13.     
  14.     } else if (A[i] - 1 == A[i-1]){
  15.       bestLower = 1 + bestHigher;
  16.       bestHigher = 1;
  17.     
  18.     } else if (A[i] + 1 == A[i-1]){
  19.       bestHigher = 1 + bestLower;
  20.       bestLower = 1;
  21.     
  22.     } else {
  23.       bestLower = 1;
  24.       bestHigher = 1;
  25.     }
  27.     best = Math.max(best, bestLower, bestHigher);
  28.   }
  29.   
  30.   return best;
  31. }
  33. arrays = [
  34.   [0, 1, 2, 1, 2, 3], // length = 4; [1,2,1,2]
  35.   [1, 2, 3, 4, 5], // length = 2; [1,2]
  36.   [1, 1, 1, 3, 3, 2, 2] // length = 4; [3,3,2,2]
  37. ];
  39. for (let arr of arrays){
  40.   console.log(JSON.stringify(arr));
  41.   console.log(f(arr));
  42. }

<!-- end snippet -->

答案2

得分: 4

  1. using System.IO;
  2. using System;
  3. using System.Collections.Generic;
  5. class Program
  6. {
  7.     static void Main()
  8.     {
  9.         List<int> arr = new List<int>() { 0, 1, 2, 1, 2, 3 };
  10.         List<int> set = new List<int>();
  11.         int n = arr.Count;
  12.         int max = 1;
  13.         int i, j;
  14.         for (i = 0; i < n - 1; i++)
  15.         {
  16.             set.Add(arr[i]);
  17.             for (j = i + 1; j < n;)
  18.             {
  19.                 if (Math.Abs(arr[i] - arr[j]) < 2)
  20.                 {
  21.                     if (!set.Contains(arr[j]))
  22.                     {
  23.                         if (set.Count == 2)
  24.                             break;
  25.                         else
  26.                             set.Add(arr[j]);
  27.                     }
  28.                 }
  29.                 else
  30.                     break;
  31.                 j++;
  32.             }
  33.             max = Math.Max(max, j - i);
  34.             set.Clear();
  35.         }
  36.         Console.WriteLine(max);
  37.     }
  38. }
英文:

C# code:

  1. using System.IO;
  2. using System;
  3. using System.Collections.Generic;
  5. class Program
  6. {
  7.     static void Main()
  8.     {
  9.         List&lt;int&gt; arr = new List&lt;int&gt;(){ 0, 1, 2, 1, 2, 3};
  10.         List&lt;int&gt; set = new List&lt;int&gt;(); 
  11.         int n = arr.Count;
  12.         int max = 1;
  13.         int i,j;
  14.         for(i=0 ; i&lt;n-1; i++)
  15.         {
  16.             set.Add(arr[i]);
  17.             for(j=i+1; j&lt;n; )
  18.             {
  19.                 if(Math.Abs(arr[i]-arr[j])&lt;2)
  20.                 {
  21.                     if(!set.Contains(arr[j]))
  22.                     {
  23.                         if(set.Count == 2)
  24.                         break;
  25.                         else
  26.                         set.Add(arr[j]);
  27.                     }  
  28.                 }
  29.                 else
  30.                 break;
  31.             j++;
  32.             }
  33.             max = Math.Max(max,j-i);
  34.             set.Clear();
  35.         }
  36.         Console.WriteLine(max); 
  37.     }
  38. }

答案3

得分: 1

参考这篇 GFG 帖子，并在其中将 X 替换为 1。

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

英文:

refer to this GFG Post
and there replace X by 1

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

答案4

得分: -3

  1. static int solution(List<Integer> arr) {
  2.     int subArrStart = 0;
  3.     int changedSubArrStart = 0;
  5.     int longSubArrayLen = 0;
  6.     int currSubArrayLen = 0;
  8.     for (int i = 0; i < arr.size(); i++) {
  9.         if (arr.get(subArrStart) == arr.get(i)) {
  10.             currSubArrayLen++;
  11.         } else if (Math.abs(arr.get(subArrStart) - arr.get(i)) == 1) {
  12.             if (subArrStart == changedSubArrStart) {
  13.                 changedSubArrStart = i;
  14.             }
  15.             currSubArrayLen++;
  16.         } else if (Math.abs(arr.get(changedSubArrStart) - arr.get(i)) == 1) {
  17.             subArrStart = changedSubArrStart;
  18.             currSubArrayLen = i - subArrStart + 1;
  19.         } else {
  20.             subArrStart = i;
  21.             changedSubArrStart = i;
  22.             currSubArrayLen = 1;
  23.         }
  25.         longSubArrayLen = Math.max(longSubArrayLen, currSubArrayLen);
  26.     }
  27.     return longSubArrayLen;
  28. }
英文:

Java solution with O(n) time complexity

static int solution(List<Integer> arr) {

  1. 	int subArrStart = 0;
  2. 	int changedSubArrStart = 0;
  4. 	int longSubArrayLen = 0;
  5. 	int currSubArrayLen = 0;
  7. 	for (int i = 0; i &lt; arr.size(); i++) {
  9. 		if (arr.get(subArrStart) == arr.get(i)) {
  10. 			currSubArrayLen++;
  11. 		} else if (Math.abs(arr.get(subArrStart) - arr.get(i)) == 1) {
  12. 			if (subArrStart == changedSubArrStart) {
  13. 				changedSubArrStart = i;
  14. 			}
  15. 			currSubArrayLen++;
  16. 		} else if (Math.abs(arr.get(changedSubArrStart) - arr.get(i)) == 1) {
  17. 			subArrStart = changedSubArrStart;
  18. 			currSubArrayLen = i - subArrStart + 1;
  19. 		} else {
  20. 			subArrStart = i;
  21. 			changedSubArrStart = i;
  22. 			currSubArrayLen = 1;
  23. 		}
  25. 		longSubArrayLen = Math.max(longSubArrayLen, currSubArrayLen);
  26. 	}
  27. 	return longSubArrayLen;
  28. }

huangapple
  • 本文由 发表于 2020年5月3日 16:43:50
  • 转载请务必保留本文链接：https://go.coder-hub.com/61571767.html
  • algorithm
  • java
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定