[leetcode] Remove Elements + Remove Duplicates from Sorted Array &amp + Remove Duplicates from Sorted List 1 & 2

Posted by: lexigrey on: November 3, 2013

• In: leetcode
• 4 Comments

几道典型two pointers一快一慢题。记住j要匀速的走，i指向最终想要的数组的最后一个元素（或者倒数第二个，或者第一个可以被change的。。因题而异）。做的挺焦躁的，记下来对比练习：

1. Remove Elements：一个数组，删掉所有出现的x，返回新长度。

• 两个pointer，一个正常走，一个指向真正去掉x的数组的长度。

• public int removeElement(int[] A, int elem) {
      int i = 0;
      for (int j = 0; j < A.length; j++) {
          if (A[j] != elem) { //should be used 
              A[i] = A[j];
              i++;
          }
      }
      return i;
  }

2. 一个排好序的数组，删掉所有重复，让新数组每个数字只出现一次，返回新数组长度。不许用额外空间。

• i指向最后一个保证valid的元素
• j指向当前exam的元素，所以从1开始；当A[j] == A[i]的时候，说明A[j]是个invalid的，所以接着走
• 可以看出来j肯定走的比i快，所以不用担心i的出界问题

• public int removeDuplicates(int[] A) {
      if (A.length == 0)
          return 0;
      int i = 0; //right most valid element
      for (int j = 1; j < A.length; j++) {
          if (A[j] != A[i]) { //when not equals to right most valid, means this is also valid, extend the valid array
              i++;
              A[i] = A[j];
          }
      }
      return i + 1; 
  }

3.每个数字最多出现两次，比如1, 1, 1, 2, 2, 3 => 1, 1, 2, 2, 3

• 同样，是当前exam的元素和valid array的最后一个（其实这里是倒数第二个）元素比较，而不是A[j]和A[j – 1]比较。后者就要混乱很多。

• public int removeDuplicates(int[] A) {
      if (A.length < 2)
          return A.length;
      int i = 1;
      for (int j = 2; j < A.length; j++) {
          if (A[j] == A[i - 1]) {
              continue;
          } else {
              i++;
              A[i] = A[j];
          }
       }
       return i + 1;
  }

4. 单链表，删除所有出现过两次或以上的元素，比如1->1->2->2->2 => null

• 同样，i指向最后一个valid元素，j是当前exam的
• 但是当A[i] == A[j]的时候，i要缩短，所以要keep一个prev pointer
• j一定要每次都往后走，保证匀速，千万别i动了j却没动。就挂在这了。

• public ListNode deleteDuplicates(ListNode head) {
      if (head == null)
          return null;
      ListNode dummy = new ListNode(0);
      dummy.next = head;
      ListNode prev = dummy, i = head, j = head.next;
      while (j != null) {
          if (i.val == j.val) {
              while (j != null && i.val == j.val) {
                  i.next = j.next; //remove j
                  j = j.next;
              }
              prev.next = i.next; //remove i
              i = prev.next;
              j = i == null ? null : i.next;
          } else {
              j = j.next;
              i = i.next;
              prev = prev.next;
          }
      }
      return dummy.next;
  }

Tags: array, list, 一快一慢双指针