从数组中删除连续元素的最有效方法是什么？Java

Question

从数组中删除连续元素的最有效方法是什么？Java

javaarraysalgorithmloopsfor-loop

3

我正在尝试以最有效的方式解决这个问题。

给定一个整数数组，不断移除其中连续三个相同的元素，直到数组中没有连续三个相同元素为止，并返回这些元素出现的次数。

例如，int[] {4,4,7,7,6,6,6,7,4} 将返回 3。当我们移除连续的 6 后，int 数组变成了 {4,4,7,7,7,4}，然后在下一轮中移除连续的 7，最终剩下了 {4,4,4}。

int[] {3,4,4,5,5,3} 将返回 0。

我已经尝试过使用不同的集合进行十几次，但被告知我的代码需要太多操作并且速度太慢。所以我想仅使用数组，但我卡住了。以下是我的代码：

    public static int getNumberOfRepetitions(int[] arr) {

    int[] arr2 = new int[arr.length];
    int counter= 0;
    int index = 0;

    for (int x= 0;x<arr.length;x++) {
        if (x < arr.length - 2) {
            if (arr[x] == arr[x + 2] && arr[x] == arr[x + 2]) {
                counter++;
                x = x + 2;
                continue;
            }
            arr2[index] = arr[x];
            index++;
        }
        if (x < arr.length - counter * 3) {
            arr = arr2;
            arr2 = new int[arr.length];
            index = 0;
            x = -1;
        }
    }
    return counter;
}

算法遍历数组并将项目添加到第二个数组中，如果有连续的元素，则将其添加到计数器中并跳过它们。在最后一次迭代中，arr被设置为arr2，for循环应该重置。

目前我无法弄清如何终止代码，所以我得到了一个无限循环。我是编程新手，希望能得到任何帮助。

- ArchibaldRajs

3

"当我们从连续的6的整数数组中删除时，变成了{4,4,7,7,7,4}。" 为什么最后一个7和4交换了位置？应该是 {4,4,7,7,4,7}，对吗？ - kaya3

@kaya3 是的，你说得对，是我的错误。 - ArchibaldRajs

这里的逻辑操作对我来说没有意义：if (arr[x] == arr[x + 2] && arr[x] == arr[x + 2])。请检查是否有打错字。 - d_air

3个回答

3

我被告知我的代码需要执行太多操作，速度太慢。这是正确的，因为实际上你可以在不修改数组的情况下完成此操作。由于这是你要完成的任务，我只会向你展示如何做到这一点，而不编写任何代码。

Initialize counter to 0, and start iterating from the beginning of the array.
Locate the next (first) triplet.
If not found, you're done, so return the counter value.
```
      start
        │  end
        │   │
4,4,7,7,6,6,6,7,4
```
You found a triplet to remove, so increment the counter by 1.

Compare the surrounding values. First compare the values right before and after.
If different, skip to step 7.

      start
        │  end
        │   │
4,4,7,7,6,6,6,7,4
      └───────┘ are they equal?

When surrounding values are equal, there are two possibilities for a cascade triplet, either an extra value before, or an extra value after.
If the extra value before/after are both different from surrounding values, skip to step 7.

      start                                start
        │  end                               │  end
        │   │                    O R         │   │
4,4,7,7,6,6,6,7,4                        4,7,6,6,6,7,7,4,4
    └─┴───────┘ are they equal?            └───────┴─┘ are they equal?

Expand the sequence to remove, and go back to step 3 to repeat the cascade search.

  start                       start
    │        end                │        end
    │         │       O R       │         │
4,4,7,7,6,6,6,7,4             4,7,6,6,6,7,7,4,4

  start                       start
    │        end                │        end
    │         │       O R       │         │
4,4,7,7,6,6,6,7,4             4,7,6,6,6,7,7,4,4
└─┴─────────────┘             └─────────────┴─┘   are they equal?

Now we need to look for a more complicated disjoint triplet.

12344433255666527
 ││└┴┘││││││││││   simple triplet found (step 2-3)
 │└───┴┘││││││││   surrounding triplet found (step 4-6)
 │      │││└┴┘││   another simple triplet found
 │      │└┴───┘│   surrounding triplet found
 └──────┴──────┘   disjoint triplet found

To do that, we need to keep track of a previous sequence removed.

  ┌ prevStart
  │    ┌ prevEnd
  │    │ ┌ start
  │    │ │    ┌ end
12344433255666527
 └──────┴──────┘   are they equal?

If the previous end is 2 positions before the new start, and the 3 values before, between, and after are the equal, then we found a disjoint triplet. Expand the sequence-to-remove to include both previous sequence, current sequence, and new triplet, then go back to step 3 to repeat the cascade search.

You have now found a section to remove, and incremented the counter the appropriate number of times, so starting after the end position, go back to step 2 to search for the next triplet.

正如您所看到的，数组从未被修改，我们只是使用索引值来处理数组。这需要比简单地修改数组并重试的方法需要更多的代码，但新代码运行得更快，因为我们不必复制数组元素。

祝你编码顺利。

- Andreas

优秀的解释和那些图示！ - royalghost

@dariosicty 非常感谢，它帮助了我，我得到了可行的解决方案并会尽快发帖！ - ArchibaldRajs

0

这里尝试使用递归方法。这类似于数组展平或查找匹配的括号，但有一个复杂性，即我们可以在删除的部分之间连接多达三个元素。

JavaScript代码经过轻微测试（欢迎提供反例/错误）：

// Returns [count, leftmostIndex]
function f(A, i=0, same=1){
  // Base case, end of list
  if (i > A.length - 1)
    return [0, A.length];
  
  // We can remove this block
  if (A[i] == A[i+1] && same == 2){
    let [count, j] = f(A, i + 2, 1);
    return [count + 1, j];
  }
    
  // Same but the count is less than
  // three, keep accumulating
  if (A[i] == A[i+1])
    return f(A, i + 1, same + 1);
  
  // Next element is different,
  // see if the next section has
  // collapsed blocks
  let [count, j] = f(A, i + 1, 1);
  
  // There is no available element
  // to try and accumulate
  if (j > A.length - 1)
    return [count, i];
    
  // The next available element
  // is the same
  if (A[i] == A[j]){
    // We've reached a count of three,
    // remove this block
    if (same == 2){
      return [count + 1, j + 1];

    // Haven't reached a count of
    // three, try one more section
    } else {
      let [count2, j2] = f(A, j + 1, 1);
      if (A[i] == A[j2])
        return [1 + count + count2, j2 + 1];
      else
        return [count + count2, i];
    }
        
  // The next available element is
  // different
  } else {
    return [count, i];
  }
}

var As = [
  [4,4,7,7,6,6,6,7,4],
  [5,7,7,7,8,4,4,5,5,6,6,6,6,6,6,5,4]
];

for (let A of As){
  console.log(JSON.stringify(A));
  console.log(JSON.stringify(A.map((_, i) => i)));
  console.log(JSON.stringify(f(A)));
}

- גלעד ברקן

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Harshal Parekh · Accepted Answer

您的逻辑存在几个问题。不必一一指出，这里提供了一个新的方法：

private static int getNumberOfRepetitions(int[] arr) {
    int[] arr2 = new int[arr.length];
    int counter= 0;
    int j = 0;
    for (int i : arr) {
        arr2[j++] = i;
        if (j > 2) {
            if (arr2[j - 1] == arr2[j - 2] && arr2[j - 1] == arr2[j - 3]) {
                counter++;
                j -= 3;
            }
        }
    }
    return counter;
}

这里，我们逐个向一个新数组中添加元素，并维护该数组的索引。当新数组中有3个元素时，比较最后3个元素。如果它们相等，则将索引("j")减3。