如何檢查均勻間隔的元素的最大數量？

我有一個數組，我的目標是找出有多少間隔11的倍數。該數組不是排序。如何檢查均勻間隔的元素的最大數量？

Such as [27, 16, 52, 84], this would return 2 
     [1, 55, 66, 33] should return 3. 
     [99, 8, 52, 32] should return 0

目前我有什麼是基本的，每個數組中元素貫穿，檢查所有其他元素與11相乘但是，這讓我在O（N²）運行時間，反正我可以優化這個？

static int eval(int [] a) { 
     int i, j, k, counter = 0; 
     for (i = 0; i < a.length; i++) { 
      for (j = 0; j < a.length; j++) { 
       if (i != j) { 
        for (k = -9; k < 10; k++) { 
         if (a[i] == a[j] + k*11) { 
          counter++; 
          break; 
         } 
        } 
       } 
      } 
     } 
    //if found nothing, will return 0, if found 1 matching, 
    //it should be 2 numbers that share this 11-difference. 
    return counter : counter == 0? 0: counter + 1; 
}

謝謝！

來源

2016-04-22 bZhang

是。你必須逐一檢查每一對。不能少於2個循環。 –

但仍然 - 你的第一個例子只有16和27.另一對是什麼？ –

是的我想我應該將它理解爲「多少個NUMBERS分享11的差異」。 16和27是2個數字，所以2 – bZhang

這不是完全清楚哪些輸出應該是比如說，[11, 22, 34, 45]。我將問題解釋爲詢問輸入的最大子集的大小，其中子集的元素之間的所有差異是11的倍數，並且大小爲1的子集不計數。

所有具有相同餘數mod 11的輸入以11的倍數間隔，因此我們只需要計算輸入中有多少個整數具有每個可能的值i % 11。這需要時間線性的輸入大小。

static int eval(int[] a) { 
    int[] inputsPerResidue = new int[11]; 
    for (int i : a) { 
     inputsPerResidue[i % 11]++; 
    } 
    int maxGroupSize = 0; 
    for (int groupSize : inputsPerResidue) { 
     if (groupSize > 1 && groupSize > maxGroupSize) { 
      maxGroupSize = groupSize; 
     } 
    } 
    return maxGroupSize; 
}

來源

2016-04-22 17:12:07 user2357112

@MikelisBaltruks：目前尚不清楚你的意思。問題陳述中的期望輸出沒有提及返回以11的倍數間隔的實際數字;它只是說要返回一個計數。 – user2357112

我的不好。讓我們剛剛刪除這些評論。：D –

這很聰明，謝謝！ – bZhang

您需要2個循環來完成此操作。計算每個元素之間的差異，如果該數字是11的倍數，則增加計數器。返回一半的櫃檯，因爲如果你打元件11二者之間的倍數，你最終會稍後再擊中循環相同的兩個要素：

static int eval(int [] a) { 
    int counter = 0; 
    for (int i = 0; i < a.length; i++) { 
     for (int j = 0; j < a.length; j++) { 
      if (i != j && Math.abs(a[i] - a[j]) % 11 == 0) { 
       counter++; 
      } 
     } 
    } 
    return counter/2; 
}

來源

2016-04-22 17:02:15

如何檢查均勻間隔的元素的最大數量？

回答

相關問題