0124-2-算法题解析与总结（四）

5.5 如何去除有序数组的重复元素

本文对应的力扣题目：

26.删除排序数组中的重复项

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

26.删除排序数组中的重复项：

int removeDuplicates(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    int slow = 0, fast = 1;
    while (fast < n) {
        if (nums[fast] != nums[slow]) {
            slow++;
            // 维护 nums[0..slow] 无重复
            nums[slow] = nums[fast];
        }
        fast++;
    }
    // 长度为索引 + 1
    return slow + 1;
}

思路：

解决数组通用技巧：尽量避免在中间删除元素，先把这个元素换到数组尾部，再一个个pop掉。时间复杂度O(1) 双指针技巧：

var removeDuplicates = function(nums) {
    // 获取数组长度
    const n = nums.length;
    // 如果数组长度为0 返回0
    if(n === 0) return 0;
    // 初始化快、慢指针
    let fast = 1, slow = 1;
    // 开始遍历
    while(fast < n){
        // 如果快指针前后 没有有重复元素
        if(nums[fast] !== nums[fast-1]){
            // 快指针的元素 赋给 慢指针
            nums[slow] = nums[fast];
            // 慢指针向前一步
            ++slow;
        }
        // 快指针继续向前走
        ++fast;
    }
    return slow;
}

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

ListNode deleteDuplicates(ListNode head) {
    if (head == null) return null;
    ListNode slow = head, fast = head.next;
    while (fast != null) {
        if (fast.val != slow.val) {
            // nums[slow] = nums[fast];
            slow.next = fast;
            // slow++;
            slow = slow.next;
        }
        // fast++
        fast = fast.next;
    }
    // 断开与后面重复元素的连接
    slow.next = null;
    return head;
}

思路：

对链表的位置需要十分了解，cur表示当前元素，cur.next表示下一个元素，cur.next.next表示下下个元素

var deleteDuplicates = function(head) {
    // 判断最后一个节点，避免死循环
    //if(head == null) return null;
    if(!head) return head;
    // 赋值给另一个变量cur
    let cur = head;
    // 开始遍历
    while(cur.next){
        // 如果当前元素cur 遇到了后面cur.next 相同的值val
        if(cur.val === cur.next.val){
            // 将cur.next从链表中移除，也就是用 下下个(cur.next.next) 赋值给 下一个(cur.next) 元素
            cur.next = cur.next.next;
        }else{
            // 否则链表中已经不存在与cur对应元素相同的节点
            // 将cur指向cur.next,下一个(cur.next) 赋值给 当前元素(cur)
            cur = cur.next;
        }
    }
    return head;
};