找到数组中相同数字之间的最大跨度
圣诞快乐，希望你精神振奋，我在Java-Arrays中有一个问题，如下所示。我坚持不懈地努力获得它。
Consider the leftmost and righmost appearances of some value in an array. We'll say that the "span" is the number of elements between the two inclusive. A single value has a span of 1. Write a **Java Function** that returns the largest span found in the given array.
**例：
maxSpan（{1,2,1,1,3}）→4，答案是4 coz MaxSpan在1到1之间是4
maxSpan（{1,4,2,1,4,1,4}）→6，答案是6考斯MaxSpan 4到4之间是6
maxSpan（{1,4,2,1,4,4,4}）→6，答案是6 coz Maxspan在4到4之间是6，大于MaxSpan在1和1之间是4，因此6> 4回答是6。
我的代码不起作用，它包含给定元素的所有Spans，我无法找到给定元素的MaxSpan。
请帮帮我。
上述计划的结果如下所示
预计此次运行
maxSpan（{1,2,1,1,3}）→4 5 X.
maxSpan（{1,4,2,1,4,1,4}）→6 8 X.
maxSpan（{1,4,2,1,4,4,4}）→6 9 X.
maxSpan（{3,3,3}）→3 5 X.
maxSpan（{3,9,3}）→3 3 OK
maxSpan（{3,9,9}）→2 3 X.
maxSpan（{3,9}）→1 1 OK
maxSpan（{3,3}）→2 3 X.
maxSpan（{}）→0 1 X.
maxSpan（{1}）→1 1 OK
：：码：：
public int maxSpan(int[] nums) { int count=1;//keep an intial count of maxspan=1 int maxspan=0;//initialize maxspan=0 for(int i=0;i<nums.length;i++){ for(int j=i+1;j<nums.length;j++){ if(nums[i] == nums[j]){ //check to see if "i" index contents == "j" index contents count++; //increment count maxspan=count; //make maxspan as your final count int number = nums[i]; //number=actual number for maxspan } } } return maxspan+1; //return maxspan }
我看到你的尝试有以下问题：
-
你的
count是完全错误的。 您可以改为从i和j计算count：j - i + 1 -
一旦你得到任何跨度，你就会覆盖
maxcount，所以你最终会得到最后一个跨度，而不是最大跨度。 通过去maxspan = Math.max(maxspan, count);修复它maxspan = Math.max(maxspan, count);。 -
你可以删除行
int number = nums[i];因为你从不使用number。 -
删除
returnmaxspan + 1中的+1;`如果你按照上面的提示删除。 -
如果数组中有任何值，则初始
maxspan应为1，如果数组为空，则为0。
这应该可以帮助你实现目标。 请注意，您可以在数组的一次传递中执行此操作，但这可能会让您感觉太过分了。 在考虑效率之前，集中精力让代码工作。
由于已经给出了解决方案，因此这是一种使用一次通过的更有效的解决方案。
public static void main(String... args) { int maxspan = maxspan(3, 3, 3, 2, 1, 4, 3, 5, 3, 1, 1, 1, 1, 1); System.out.println(maxspan); } private static int maxspan(int... ints) { Map first = new LinkedHashMap(); // use TIntIntHashMap for efficiency. int maxspan = 0; // max span so far. for (int i = 0; i < ints.length; i++) { int num = ints[i]; if (first.containsKey(num)) { // have we seen this number before? int span = i - first.get(num) + 1; // num has been found so what is the span if (span > maxspan) maxspan = span; // if the span is greater, update the maximum. } else { first.put(num, i); // first occurrence of number num at location i. } } return maxspan; }
这是这个问题的解决方案：
public int maxSpan(int[] nums) { int maxSpan=0; int tempSpan=0; if(nums.length==0){ return 0; } for(int i=0;ii;j--){ if(nums[i]==nums[j]){ tempSpan=ji; break; } } if(tempSpan>maxSpan){ maxSpan=tempSpan; } } return maxSpan+1; }
我用List做了。 更简单的方法。 唯一的问题是如果arrays太大，可能需要一段时间..
import java.util.ArrayList; import java.util.List; public class StackOverflow { public static void main(String[] args) { List listNumbers = new ArrayList (); listNumbers.add(3); listNumbers.add(3); listNumbers.add(3); listNumbers.add(2); listNumbers.add(1); listNumbers.add(4); listNumbers.add(3); listNumbers.add(5); listNumbers.add(1); listNumbers.add(1); listNumbers.add(1); listNumbers.add(1); listNumbers.add(1); listNumbers.add(3); int result = 0; Integer key = null; for(Integer i : listNumbers){ int resultDistance = returnDistance(listNumbers, i); if (resultDistance > result){ result = resultDistance; key = i; } } System.out.println("MaxSpan of key " + key + " is: " + result); } private static int returnDistance(List listNumbers, Integer term){ Integer startPosition = null; Integer endPosition = null; boolean bolStartPosition = false; boolean bolResult = false; int count = 1; int result = 0; for (Integer i : listNumbers){ if (i == term && !bolStartPosition){ startPosition = count; bolStartPosition = true; continue; } if (i == term && bolStartPosition){ endPosition = count; } count++; } if (endPosition != null){ // because it's inclusive from both sides result = endPosition - startPosition + 2; bolResult = true; } return (bolResult?result:-1); } }
一个powershell解决方案可能是这样的，从数组中取出一个item ，并从最左边找到第一个item ，并计算跨度，然后与之前的结果进行比较。
public int maxSpan(int[] nums) { int result = 0; for(int i = 0; i < nums.length; i++) { int item = nums[i]; int span = 0; for(int j = 0; j<= i; j++) {//find first occurance of item from the left if(nums[j]==item) { span = i -j+1; break; } } if(span>result) { result = span; } } return result; }
这是解决方案 –
public int maxSpan(int[] nums) { int span = 0; for (int i = 0; i < nums.length; i++) { for(int j = i; j < nums.length; j++) { if(nums[i] == nums[j]) { if(span < (j - i + 1)) { span = j -i + 1; } } } } return span; }
public int maxSpan(int[] nums) { //convert the numnber to a string String numbers = ""; if (nums.length == 0) return 0; for(int ndx = 0; ndx < nums.length;ndx++){ numbers += nums[ndx]; } //check beginning and end of string int first = numbers.indexOf(numbers.charAt(0)); int last = numbers.lastIndexOf(numbers.charAt(0)); int max = last - first + 1; int efirst = numbers.indexOf(numbers.charAt(numbers.length()-1)); int elast = numbers.lastIndexOf(numbers.charAt(numbers.length()-1)); int emax = elast - efirst + 1; //return the max span. return (max > emax)?max:emax; }
public int maxSpan(int[] nums) { int current = 0; int currentcompare = 0; int counter = 0; int internalcounter = 0; if(nums.length == 0) return 0; for(int i = 0; i < nums.length; i++) { internalcounter = 0; current = nums[i]; for(int x = i; x < nums.length; x++) { currentcompare = nums[x]; if(current == currentcompare) { internalcounter = x - i; } if(internalcounter > counter) { counter = internalcounter; } } } return counter + 1; }
public int maxSpan(int[] nums) { if(nums.length<1){ return 0; } int compare=1; for (int i=0; i=compare){ compare = Math.abs(l)-Math.abs(i)+1; } } } return compare; }
public static int MaxSpan(int[] input1, int key) { int Span = 0; int length = input1.length; int i,j,k = 0; int start = 0, end = 0 ; k = key; for (int l = 0; l < length; l++) { if(input1[l] == k) { start = l; System.out.println("\nStart = " + start); break; } } if(start == 0) { Span = 0; System.out.println("Key not found"); return Span;} for (j = length-1; j> start; j--) { if(input1[j] == k) { end = j; System.out.println("\nEnd = " + end); break; } } Span = end - start; System.out.println("\nStart = " + start + "End = " + end + "Span = " + Span); return Span; }
public int maxSpan(int[] nums) { int length = nums.length; if(length <= 0) return 0; int left = nums[0]; int rigth = nums[length - 1]; int value = 1; //If these values are the same, then the max span is length if(left == rigth) return length; // the last match is the largest span for any value for(int x = 1; x < length - 1; x++) { if(nums[x] == left || nums[x] == rigth) value = x + 1; } return value; }
public int maxSpan(int[] nums) { int count, largest=0; for (int x=0; x< nums.length; x++) { for (int y=0; y< nums.length; y++) { if (nums[x]==nums[y]) { count= y-x+1; if (count > largest) { largest= count; } } } } return largest; }
import java.io.*; public class maxspan { public static void main(String args[])throws java.io.IOException{ int A[],span=0,pos=0; DataInputStream in=new DataInputStream(System.in); System.out.println("enter the number of elements"); A=new int[Integer.parseInt(in.readLine())]; int i,j; for(i=0;i=0;j--) if(A[i]==A[j]&&(ji)>span){span=ji;pos=i;} } System.out.println("maximum span => "+(span+1)+" that is of "+A[pos]); } }
public static int maxSpan(int[] nums) { int left = 0; int right = 0; for (int i = 0; i < nums.length; i++) { if (nums[0] == nums[nums.length - 1 - i]) { left = nums.length - i; break; } else if (nums[nums.length - 1] == nums[i]) { right = nums.length - i; break; } } return Math.max(left, right); }
上面的解决方案很棒，如果你的目标是避免使用Arrays.asList和indexOf以及LastIndexOf，下面的代码尽可能地使工作变得懒惰，同时仍然清晰简洁。
public int maxSpan(int[] nums) { if(nums.length < 2){ //weed out length 0 and 1 cases return nums.length; } int maxSpan = 1; //start out as 1 for(int a = 0; a < nums.length; a++){ for(int b = nums.length - 1; b > a; b--){ if(nums[a] == nums[b]){ maxSpan = Math.max(maxSpan, (b + 1 - a)); //A little tricky getting those indices together. break; //there's no reason to continue, //at least for this single loop execution inside another loop } } } return maxSpan; //the maxSpan is here! } The Math.max method returns the larger of 2 values, one of them if they are equal.
这就是我做的方式：
public int maxSpan(int[] nums) { for (int span=nums.length; span>0; span--) { for (int i=0; i
我不确定，如果我必须使用2个for-loops ……或者任何循环呢？
如果没有，这个版本的function没有任何循环。
首先检查，如果数组的长度> 0.如果不是，则只返回数组的长度，这将对应于正确的答案。
如果长度大于0，则检查数组中的第一个和最后一个位置是否具有相同的值。
如果是，则返回数组的长度作为maxSpan 。
如果不是，则减去1，因为该值在数组中出现两次。
完成。
public int maxSpan(int[] nums) { if(nums.length > 0){ if(nums[0] == nums[nums.length - 1]){ return nums.length; } else{ return nums.length - 1; } } return nums.length; }
public int maxSpan(int[] nums) { int b = 0; if (nums.length > 0) { for (int i = 0; i < nums.length; i++) { int a = nums[0]; if (nums[i] != a) { b = nums.length - 1; } else { b = nums.length; } } } else { b = 0; } return b; }
public int maxSpan(int[] nums) { Stack stack = new Stack(); int count = 1; int value = 0; int temp = 0; if(nums.length < 1) { return value; } for(int i = 0; i < nums.length; i++) { for(int j = nums.length - 1; j >= i; j--) { if(nums[i] == nums[j]) { count = (j - i) + 1; stack.push(count); count = 1; break; } } } if(stack.peek() != null) { while(stack.size() != 0) { temp = (Integer) stack.pop(); if(value <= temp) { value = temp; } else { value = value; } } } return value; }
public int maxSpan(int[] nums) { int totalspan=0; int span=0; for(int i=0;ii-1;j--) { if(nums[i]==nums[j]) { span=j-i+1; if (span>totalspan) totalspan=span; break; } } } return totalspan; }
public int maxSpan(int[] nums) { int max_span=0, j; for (int i=0; imax_span) max_span=j-i+1; } return max_span; }
带有Map线性解决方案，用于存储第一次出现，并计算下次出现的距离：
public int maxSpan(int[] nums) { int span = 0; Map first = new HashMap(); for (int i = 0; i < nums.length; i++) { if (!first.containsKey(nums[i])) first.put(nums[i], i); span = Math.max(span, (i - first.get(nums[i])) + 1); } return span; }