Easy if you use loop invariants


  • 2
    L

    It's very simple if you think in terms of invariants. For example:

    Array is partitioned into three parts:

    1. The leftmost part consists of the already deduplicated elements, start as index 0 ends at index i.

    2. Middle part of the array are the duplications, it ends at index j.

    3. And the rightmost part starts at j, ends at n and contains not yet examined elements.

      class Solution {
      public:
      int removeDuplicates(int A[], int n) {
      if(n==0)
      return 0;
      int i=1;
      for(int j=1;j<n;++j)
      {
      if(A[i-1] != A[j])
      A[i++] = A[j];
      }
      return i;
      }
      };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.