原地修改数组

26. 删除有序数组中的重复项 (opens new window)

83. 删除排序链表中的重复元素 (opens new window)

27. 移除元素 (opens new window)

283. 移动零 (opens new window)

我们知道对于数组来说，在尾部插⼊、删除元素是⽐较⾼效的，时间复杂度是 O(1)，但是如果在中间或者开 头插⼊、删除元素，就会涉及数据的搬移，时间复杂度为 O(N)，效率较低。

所谓原地修改，就是不允许我们 new 新数组，只能在原数组上操作，然后返回⼀个⻓度，这样就可以通过返回的长度和原始数组得到我们去重后的元素有哪些了。

删除有序数组中的重复项

题目：

思想：

由于这个是一个升序排列的数组，那么相同的元素肯定是在一起的，但是就如同我们前言所说如果在数组中间对元素进行修改，时间复杂度较高，这里我们就采用双指针的快慢指针，让快指针在前面探路，慢指针在后，如果快慢指针所对应的元素相同，慢指针不动，快指针后移，如果不相同，慢指针后移一位，记录当前快指针元素，快指针继续后移，不断循环，当快指针超过数组长度的时候，循环结束。

代码：

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length == 0) {
            return 0;
        }
        int fast = 0;
        int slow = 0;
        for(;fast < nums.length; fast++) {
            if(nums[slow] != nums[fast]) {
                slow++;
                nums[slow] = nums[fast];
            }
        }
        return slow + 1;
    }
}

删除排序链表中的重复元素

题目：

思想：

和上一题类似，只是这边使用了链表，还是使用快慢指针的方式。

代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null) {
            if(slow.val != fast.val) {
                slow = slow.next;
                slow.val = fast.val;
            }
            fast = fast.next;
        }
        slow.next = null;
        return head;
    }
}

移除元素

题目：

思想：

这个题不同的是要移除元素，所以在判断那里有些特别。因为是要移除元素，所以先赋值，后移动慢指针。

代码：

class Solution {
    public int removeElement(int[] nums, int val) {
        if(nums.length == 0) {
            return 0;
        }        
        int fast = 0;
        int slow = 0;
        while(fast < nums.length) {
            if(nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
}

移动零

题目：

思想：

此题就是在快慢指针的基础上，进行元素的交换，当快指针所对应的元素不是0的时候，两个指针一起往后走，当慢指针所对应的元素为0的时候，两指针所对应的元素进行交换即可。

代码：

class Solution {
    public void moveZeroes(int[] nums) {
        if(nums.length == 0) {
            return;
        }
        int fast = 0, slow = 0;
        while(fast < nums.length) {
            if(nums[fast] != 0) {
                if(nums[slow] == 0) {
                   int temp = nums[fast];
                    nums[fast] = nums[slow];
                    nums[slow] = temp;
                }   
                slow++;
            }
            fast++;
        }

    }
}

class Solution {
    public void moveZeroes(int[] nums) {
        int p = removeElement(nums, 0);
        // 将 p 之后的所有元素赋值为 0
        for (; p < nums.length; p++) {
            nums[p] = 0;
        }
    }
    public static int removeElement(int[] nums, int val) {
        int fast = 0, slow = 0;
        while (fast < nums.length) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
}

第二种方法就是利用前面的移除元素，我们把0的元素移除，然后从返回的新长度遍历到原始的长度，把这个范围的元素全部置为0即可。

参考

如何去除有序数组的重复元素 (opens new window)