Void-7's

LeetCode-26/80 删除排序数组中的重复项 I/II

leetcode

太菜了,在简单题和中等题上花了好久去想,中间也写出了第80题的非常丑陋的版本,就不贴上来了。 实际上还是下面这种思想最容易理解: 两个题目虽然一个重复1次,一个重复2次,但是用双指针的思想,low指针的作用都是一致的, 我们用low指针来指向已处理元素部分的最后一组元素,因为在80题中,最大可以重复2次, **也就是说我们不在乎相邻两个元素是否相等,只需要保证相隔一个的两元素不相等。**因为如果 相隔一个的两元素都相等,那么这对元素和中间夹的元素都相等,已经冗余,这时候把high的元素 拷贝到low+2的位置就是正确的做法。 所以我们第一步就可以让low从索引0(第一个位置)开始,high从low+2(第三个位置)开始, 一共循环(数组的长度-2)次。当循环最后一次结束,low+1的位置必定是数组的结尾,所以返回 的数组长度就是low+1+1=low+2

/*
  每个元素最多出现1次
  空间复杂度O(1),时间复杂度O(N)
*/
function unique(arr) {
  if (arr.length == 1) return arr;
  let cnt = 0;
  for (let i = 0; i < arr.length; i++) {
    //当i项元素与后一项元素不等时,将arr[i]拷贝到arr[cnt]
    if (i < arr.length - 1 && arr[i] != arr[i + 1]) 
      arr[cnt++] = arr[i];
  }
  //这种循环判断语句最后会剩下末尾那一个元素
  arr[cnt++] = arr[arr.length-1];
  return cnt;
}

//初始版本的边界条件判断有点丑陋,简化如下:
//每当low和high指向的元素不等,arr[++low]=arr[high]
function unique2(arr){
  if (arr.length <= 1) return arr;
  let low=0;
  for(let high=1;high<arr.length;high++){
    //low指向已去重部分的最后一项
    if(arr[low]!=arr[high]) arr[++low]=arr[high];
  }
  return low+1;
}


let s = [0,0,1,1,1,1,2,3,3];
print(s,unique(s));

s = [0,0,1,1,1,1,2,3,3];
print(s,unique2(s));

/*
  每个元素最多出现2次
  >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  leetcode-80 删除有序数组中的重复项 II

  给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 最多出现两次 ,返回删除后数组的新长度。
  不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

  示例 1:

  输入:nums = [1,1,1,2,2,3]
  输出:5, nums = [1,1,2,2,3]
  解释:函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。

  示例 2:

  输入:nums = [0,0,1,1,1,1,2,3,3]
  输出:7, nums = [0,0,1,1,2,3,3]
  解释:函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。

  提示:

      0 <= nums.length <= 3 * 104
      -104 <= nums[i] <= 104
      nums 已按升序排列
  >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
*/

/* leetcode-26 最多重复1次 */ 
//
// var removeDuplicates = function(nums) {
//   let l=0;
//   if(nums.length==1) return 1;
//   for(let h=1;h<nums.length;h++){
//       if(nums[l]!=nums[h]) nums[++l]=nums[h];
//   }
//   return l+1;
// };

var removeDuplicates = function(nums) {
  let l=1;
  if(nums.length<=2) return nums.length;
  for(let h=2;h<nums.length;h++){
      if(nums[l]!=nums[h]) {
        if((l+2)!=h) nums[l+2]=nums[h];
        l++;
      }
  }
  return l+2;
};

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
let nums = [0,0,1,1,1,1,2,3,3];
print(nums,removeDuplicates(nums));

function print(arr,n){
  arr.length=n;
  console.log(arr);
}