美文网首页让前端飞Web前端之路
大厂面试高频题:如何去除有序数组的重复元素

大厂面试高频题:如何去除有序数组的重复元素

作者: 一一秋风 | 来源:发表于2021-02-05 17:39 被阅读0次
function removeDuplicates(nums) {
    let n = nums.length;
    if (n == 0) return 0;
    let 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;
}
let nums=[1, 2, 3, 4, 4, 5, 5, 5,33,33]
console.log(nums.slice(0,removeDuplicates(nums)))

思路

我们让慢指针 slow 走左后面,快指针 fast 走在前面探路,找到一个不重复的元素就告诉 slow 并让 slow 前进一步。这样当 fast 指针遍历完整个数组 nums 后,nums.slice(0,slow) 就是不重复元素,之后的所有元素都是重复元素。

链表

let deleteDuplicates=(head)=>{
  if(head == null)
  return null;
  let slow=head
  let fast=head.next
  while(fast!=null){
      if(slow.val!=fast.val){
        slow.next=fast
        slow=slow.next
      }  
      fast=fast.next()
  }
  slow.next=null;
  return head
}

相关文章

网友评论

    本文标题:大厂面试高频题:如何去除有序数组的重复元素

    本文链接:https://www.haomeiwen.com/subject/wqrgtltx.html