如何在整数数组中找到重复的整数序列？

Question

如何在整数数组中查找重复的整数序列？

00 会重复，123123 也会重复，但 01234593623 不会。

我有一个想法如何做到这一点，但我的脑海里很模糊，因此我的实施并没有走得太远。

我的想法是

每次执行 for 循环时偏移一定量
在其中循环并通过该偏移量比较数字块

在 Java 中，我走到了这一步：

    String[] p1 = new String[nDigitGroup];
    String[] p2 = new String[nDigitGroup];

    for (int pos = 0; pos < number.length - 1; pos++)
    {
        System.out.println("HERE: " + pos + (nDigitGroup - 1));
        int arrayCounter = -1;

        for (int n = pos; n < pos + nDigitGroup ; n++)
        {
            System.out.printf("\nPOS: %d\nN: %d\n", pos, n);
            arrayCounter++;
            p1[arrayCounter] = number[n];

            System.out.println(p1[arrayCounter]);
        }

        pos += nDigitGroup;
        arrayCounter = -1;

        System.out.println("SWITCHING");

        for (int n = pos; n < pos + nDigitGroup ; n++)
        {
            System.out.printf("\nPOS: %d\nN: %d\n", pos, n);
            arrayCounter++;
            p2[arrayCounter] = number[n];

            System.out.println(p2[arrayCounter]);
        }

        if (p1[0].equals(p2[0]) && p1[1].equals(p2[1])) System.out.println("MATCHING");
    }

当运行使用这些参数时：

        repeatingSeqOf(2, new String[] {"1", "2", "3", "4", "5", "6", "7", "7" });

我正确地填充了节数组，但它在索引越界异常时中断。

Answer 1

试试这个：

string lookIn = "99123998877665544123"; 
// above has length of 20 (in positions 0 through 19)
int patternLength = 3;
// want to search each triple of letters 0-2, 1-3, 2-4 ... 17-19
//   however since there must be 3 chars after the 3-char pattern
//   we only want to search the triples up to 14-16 (20 - 3*2)
for (int i=0; i <= lookIn.Length - patternLength * 2; i++) {
   string lookingFor = lookIn.Substring(i, patternLength);
   // start looking at the pos after the pattern
   int iFoundPos = lookIn.IndexOf(lookingFor, i + patternLength);
   if (iFoundPos > -1) {
      string msg = "Found pattern '" + lookingFor 
                 + "' at position " + i 
                 + " recurs at position " + iFoundPos;
   }
}
// of course, you will want to validate that patternLength is less than
//   or equal to half the length of lookIn.Length, etc.

编辑：改进并转换为 javascript（来自 C#...哎呀，对此感到抱歉...）

function testfn() {
   var lookIn = "99123998877665544123"; 
   // above has length of 20 (in positions 0 through 19)
   var patternLength_Min = 2;
   var patternLength_Max = 5;
   if (patternLength_Max > (lookIn.length / 2) 
                || patternLength_Max < patternLength_Min
                || patternLength_Min < 1) {
      alert('Invalid lengths.')
   }
   var msg = "";
   for (var pLen = patternLength_Min; pLen <= patternLength_Max; pLen++)  {
      for (var i = 0; i <= lookIn.length - pLen * 2; i++) {
         var lookingFor = lookIn.substring(i, i + pLen);
         // start looking at the pos after the pattern
         var iFoundPos = lookIn.indexOf(lookingFor, i + pLen);
         if (iFoundPos > -1) {
            msg = msg + "Found '" + lookingFor 
                       + "' at pos=" + i 
                       + " recurs at pos=" + iFoundPos + "\n";
            ;
         }
      }
   }
   alert(msg);
}

消息框显示如下：

Found '99' at pos=0 recurs at pos=5
Found '12' at pos=2 recurs at pos=17
Found '23' at pos=3 recurs at pos=18
Found '123' at pos=2 recurs at pos=17

Answer 2

您可以随时使用正则表达式来获得所需的结果。使用 regex backreference 并将其与贪婪量词组合：

    void printRepeating(String arrayOfInt)
    {
        String regex = "(\d+)\1";
        Pattern patt = Pattern.compile(regex);
        Matcher matcher = patt.matcher(arrayOfInt);           
        while (matcher.find())                              
        {               
            System.out.println("Repeated substring: " + matcher.group(1));
        } 
    }

Answer 3

@MiljenMikic 的回答很棒，特别是因为语法实际上并不规则。 :D

如果您想在一般数组上执行此操作，或者想了解它，这与正则表达式的功能几乎完全相同：

public static void main(String[] args) {
    int[] arr = {0, 1, 2, 3, 2, 3}; // 2, 3 repeats at position 2.

    // for every position in the array:
    for (int startPos = 0; startPos < arr.length; startPos++) {
        // check if there is a repeating sequence here:

        // check every sequence length which is lower or equal to half the
        // remaining array length: (this is important, otherwise we'll go out of bounds)
        for (int sequenceLength = 1; sequenceLength <= (arr.length - startPos) / 2; sequenceLength++) {

            // check if the sequences of length sequenceLength which start
            // at startPos and (startPos + sequenceLength (the one
            // immediately following it)) are equal:
            boolean sequencesAreEqual = true;
            for (int i = 0; i < sequenceLength; i++) {
                if (arr[startPos + i] != arr[startPos + sequenceLength + i]) {
                    sequencesAreEqual = false;
                    break;
                }
            }
            if (sequencesAreEqual) {
                System.out.println("Found repeating sequence at pos " + startPos);
            }
        }
    }
}

Answer 4

@AdrianLeonhard 发布的答案非常有效。但是如果我有一系列 0、1、2、3、4、3、5、6、4、7、8、7、8 许多人可能想知道如何从数组中获取所有重复的数字。

所以，我写了这个简单的逻辑，打印所有重复的数字及其位置

    int[] arr = {0, 1, 2, 3, 4, 3, 5, 6, 4, 7, 8, 7, 8};

    for(int i=0; i<arr.length;i++){
        for(int j=i+1; j<arr.length;j++){
            if(arr[i] == arr[j]){
                System.out.println("Number: "+arr[i]+" found repeating at position: "+i+" , repeated at position "+j);
            }
        }
    }

如何在整数数组中找到重复的整数序列？

How to find repeating sequence of Integers in an array of Integers?

java

arrays

algorithm

math