分享一个删除所有指定元素的方法

Question

void removeElementAll(T e) {
    for (int i = 0; i < size; i++) {
        if ( data[i] == e ) {
            remove(i);	
            i--; 	// 与后面的 i++ 相抵消
        }
    }
 }

Answer 1

liuyubobobo 2020-08-06 17:13:21

可以。但我要是没有理解错，remove(i) 又是一个 O(n) 的过程。所以整个函数是一个 O(n^2) 的过程了。不过删除所有和 e 相等的元素可以做到 O(n) 解决：）

继续加油！：）

• 提问者 慕用0058068 #1

  啊，看来我还是经验不够，没往提升性能这方面想，多谢 bobo 老师指点。
  现在补充一个 O(n) 的写法：
  
  ```C++
  
  void removeElementAll(T e) {
      int i = 0;
      int j = 0;
      int removedN = 0;  // 用于记录需要被删除的元素的个数
      while ( j < size ) {
          if ( data[j] != e )
              data[i++] = data[j++];
          else {
              removedN++;
              j++;
          }
      }
      size - removedN;
  }
  
  ```