找到数组中相同数之间的最大跨度

Merry Christmas and hope you are in great Spirits,I have a Question in Java-Arrays as shown below.Im stuck up with this struggling to get it rite.

圣诞快乐，希望你心情愉快，我在java -数组中有一个问题，如下所示。我挣扎着要把它弄成仪式。

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.

考虑数组中某个值的最左和最右的外观。我们会说“span”是两个包含元素之间的个数。一个值的跨度为1。编写一个**Java函数**，返回给定数组中最大的跨度。

**Example:
maxSpan({1, 2, 1, 1, 3}) → 4,answer is 4 coz MaxSpan between 1 to 1 is 4
maxSpan({1, 4, 2, 1, 4, 1, 4}) → 6,answer is 6 coz MaxSpan between 4 to 4 is 6
maxSpan({1, 4, 2, 1, 4, 4, 4}) → 6,answer is 6 coz Maxspan between 4 to 4 is 6 which is greater than MaxSpan between 1 and 1 which is 4,Hence 6>4 answer is 6.

* *的例子:maxSpan({ 1、2、1,1,3 })→4,答案是4 1到1之间因为maxSpan maxSpan({ 1、4、2、1、4、1、4 })→6,答案是6 4 - 4之间因为maxSpan 6 maxSpan({ 1、4、2、1,4,4,4 })→6,答案是6 4 - 4之间因为maxSpan 6之间大于maxSpan 1和1 4,因此6 > 4的答案是6。

I have the code which is not working,it includes all the Spans for a given element,im unable to find the MaxSpan for a given element.

我有不工作的代码，它包含给定元素的所有跨度，我无法找到给定元素的MaxSpan。

Please help me out.

请帮帮我。

Results of the above Program are as shown below

上述程序的结果如下所示。

Expected This Run
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

预计这次运行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好maxSpan({ 3、9、9 })→2 3 X maxSpan({ 3、9 })→1 1好maxSpan({ 3 3 })→2 3 X maxSpan({ })→0 1 X maxSpan({ 1 })→1 1好

::Code::

::代码::

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        
}    

22 个解决方案

#1

I see the following problems with your attempt:

我发现你的尝试存在以下问题:

• Your count is completely wrong. You can instead calculate count from i and j: j - i + 1

  你的数目完全错了。你可以用i和j计算count: j - i + 1

• You're overriding maxcount as soon as you get any span, so you're going to end up with the last span, not the maximum span. Fix it by going maxspan = Math.max(maxspan, count);.

  只要有张成空间，就会覆盖maxcount，所以最后的张成空间是最后一个张成的，而不是最大张成的。通过maxspan = Math修正它。马克斯(maxspan计数);。

• You can remove the line int number = nums[i]; as you never use number.

  可以删除线int数= nums[i];因为你从来不使用数字。

• Remove the +1 in the returnmaxspan+1;` if you follow my tips above.

  删除returnmaxspan+1中的+1;'如果您遵循我上面的提示。

• Initial maxspan should be 1 if there are any values in the array, but 0 if the array is empty.

  如果数组中有任何值，初始maxspan应该是1，但如果数组为空，则为0。

That should help you get it working. Note that you can do this in a single pass of the array, but that's probably stretching it too far for you. Concentrate on getting your code to work before considering efficiency.

这将帮助你让它工作。请注意，您可以在数组的一次遍历中执行此操作，但这可能对您来说太过分了。在考虑效率之前，集中精力让代码工作。

#2

Since a solution has been given, here is a more efficient solution which uses one pass.

由于已经给出了一个解决方案，这里有一个更有效的解决方案，它使用一次遍历。

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<Integer, Integer> first = new LinkedHashMap<Integer, Integer>(); // 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;
}

#3

Here is the solution of this problem:

下面是这个问题的解决方案:

public int maxSpan(int[] nums) {
        int maxSpan=0;
        int tempSpan=0;

        if(nums.length==0){
            return 0;
        }

        for(int i=0;i<nums.length;i++){   
            for(int j=nums.length-1;j>i;j--){ 
                if(nums[i]==nums[j]){
                    tempSpan=j-i;
                    break;
                } 
            } 
            if(tempSpan>maxSpan){
                maxSpan=tempSpan;
            } 
        } 
        return maxSpan+1;
    }

#4

I did it with a List. Easier way to do it. The only problem is if the Array is too big, maybe it's gonna take a while..

我做了一个列表。更简单的方法。唯一的问题是如果数组太大，可能需要一段时间。

import java.util.ArrayList;
import java.util.List;


public class * {

    public static void main(String[] args) {
        List<Integer> listNumbers = new ArrayList<Integer>();
        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<Integer> 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);
    }
}

#5

One brute force solution may like this, take one item from the array, and find the first occurance of item from the left most, and calculate the span, and then compare with the previous result.

一个蛮力解决方案可能是这样的，从数组中取出一个项，然后从最左边找到第一个项的出现，然后计算跨度，然后与前面的结果进行比较。

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;
}

#6

Here is the solution -

这就是答案

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;
}

#7

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;
}

#8

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;
}

#9

public int maxSpan(int[] nums) {
if(nums.length<1){
return 0;
}
int compare=1;
for (int i=0; i<nums.length; i++){
for (int l=1; l<nums.length; l++){
if((nums[l]==nums[i])&&(Math.abs(l)-Math.abs(i))>=compare){
compare = Math.abs(l)-Math.abs(i)+1;
}
}
}  
return compare;
}

#10

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;
}  

#11

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;
}

#12

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;
}

#13

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<A.length;i++)
        {
            A[i]=Integer.parseInt(in.readLine());
        }
        for(i=0;i<A.length;i++)
        {
            for(j=A.length-1;j>=0;j--)
                if(A[i]==A[j]&&(j-i)>span){span=j-i;pos=i;}
        }
        System.out.println("maximum span => "+(span+1)+" that is of "+A[pos]);

    }
}

#14

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);
}

#15

The above solutions are great, if your goal is to avoid using Arrays.asList and indexOf and LastIndexOf, the code below does the job as lazy as possible, while still being clear and concise.

如果您的目标是避免使用数组，那么上面的解决方案是很好的。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.

#16

This is how I did it:

我就是这样做的:

public int maxSpan(int[] nums) {
  for (int span=nums.length; span>0; span--) {
    for (int i=0; i<nums.length-span+1; i++) {
      if (nums[i] == nums[i+span-1]) return span;
    }
  }
  return 0;
}

#17

I am not sure, if I have to use 2 for-loops... or any loop at all?

我不确定，如果我必须使用2 for循环…或者任何循环?

If not, this version functions without any loop.

如果没有，这个版本就没有任何循环。

At first you check, if the length of the array is > 0. If not, you simply return the length of the array, which will correspond to the correct answer.

首先检查数组的长度是否为>。如果不是，您只需返回数组的长度，这将对应于正确的答案。

If it is longer than 0, you check if the first and last position in the array have the same value.

如果它大于0，则检查数组中的第一个和最后一个位置是否具有相同的值。

If yes, you return the length of the array as the maxSpan.

如果是，则返回数组的长度作为maxSpan。

If not, you substract a 1, since the value appears twice in the array.

如果不是，则减1，因为值在数组中出现了两次。

Done.

完成了。

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;
}

#18

   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;
}

#19

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;
}

#20

public int maxSpan(int[] nums) {
  int totalspan=0;
  int span=0;
  for(int i=0;i<nums.length;i++)
  {
    for (int j=nums.length-1;j>i-1;j--)
    {
      if(nums[i]==nums[j])
      {
      span=j-i+1;
      if (span>totalspan)
      totalspan=span;
      break;
      }
    }
  }
  return totalspan;
}

#21

public int maxSpan(int[] nums) {
  int max_span=0, j;
  for (int i=0; i<nums.length; i++){
    j=nums.length-1;
    while(nums[i]!=nums[j]) j--;
    if (j-i+1>max_span) max_span=j-i+1;
  }
  return max_span;
}

#22

Linear solution with a Map storing the first occurrence, and calculating the distance from it for the next occurrences:

将第一个事件存储在地图上的线性解决方案，并计算下一个事件的距离:

public int maxSpan(int[] nums) {
  int span = 0;
  Map<Integer, Integer> first = new HashMap<Integer, Integer>();
  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;
}