Jamzen的技术博客
0%

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

发表于 分类于 Valine：

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

示例 1：
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
object RemoveDuplicates {

     def main(args: Array[String]): Unit = {
          val nums = Array[Int](2, 2, 2)
          println(removeDuplicates(nums))
          println(java.util.Arrays.toString(nums))

          val nums1 = Array(4, 2, 2)
          println(removeDuplicates(nums1))
          println(java.util.Arrays.toString(nums1))

          val nums2 = Array(0, 1, 1, 1, 2, 3, 3, 3, 3, 4)
          println(removeDuplicates(nums2))
          println(java.util.Arrays.toString(nums2))

          val nums3 = Array(0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3)
          println(removeDuplicates(nums3))
          println(java.util.Arrays.toString(nums3))

     }

     def removeDuplicates(nums: Array[Int]): Int = {
          if (nums.length <= 2) return nums.length
          var i = 0
          var s = 0
          var e = 1
          while (e < nums.length) {
               while (e < nums.length && nums(s) == nums(e)) {
                    e += 1
               }
               nums(i) = nums(s)
               i += 1
               if (e >= s + 2) {
                    nums(i) = nums(s)
                    i += 1
               }
               s = e
          }
          i
     }
}