java 查找数组中相同数字之间的最大跨度

Find the largest span between the same number in an array

提问by Deepak

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.

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.

**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,answer is 4 coz MaxSpan between 1 to 1 is 4
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 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

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

回答by Peter Lawrey

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

回答by mukul28.03

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

回答by moinudin

I see the following problems with your attempt:

我发现您的尝试存在以下问题：

• Your countis completely wrong. You can instead calculate countfrom iand j: j - i + 1

• You're overriding maxcountas soon as you get anyspan, so you're going to end up with the lastspan, not the maximumspan. Fix it by going maxspan = Math.max(maxspan, count);.

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

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

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

• 你count完全错了。您可以改为count从i和计算j：j - i + 1

• 你覆盖了maxcount，一旦你得到任何跨度，所以你会与结束了最后一个跨度，而不是最大跨度。去修复它maxspan = Math.max(maxspan, count);。

• 您可以删除该行，int number = nums[i];因为您从不使用number.

• 取出+1在returnmaxspan + 1;`如果你按照我上面的提示。

• 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.

这应该可以帮助你让它工作。请注意，您可以在一次数组中完成此操作，但这可能对您来说太过分了。在考虑效率之前专注于让您的代码工作。

回答by Gondim

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..

我是用 List 做的。更简单的方法。唯一的问题是如果 Array 太大，可能需要一段时间。

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


public class StackOverflow {

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

回答by Honwhy Wang

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

一个蛮力解决方案可能是这样的，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;
}

回答by Praful Surve

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

回答by muradul mostafa

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

回答by James

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

回答by Akshay Sapra

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

回答by Necati S?zer

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