乐趣区

关于leetcode:LeetCodeGolang-27移除元素

jiezi

题目：

给你一个数组 nums 和一个值 val，你须要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要应用额定的数组空间，你必须仅应用 O(1) 额定空间并 原地 批改输出数组。

元素的程序能够扭转。你不须要思考数组中超出新长度前面的元素

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

题解：

首先，这是一道数组类的简略算法题。咱们明确循环不变式（loop invariant）的概念，即一组在循环体内、每次迭代均放弃为真的性质。

先贴代码：（GO 语言）

func removeElement(nums []int, val int) int {left, right, n := 0, 0, len(nums)
   for right < n {if nums[right] != val {nums[left] = nums[right]
         left++
      }
      right++
   }
   return left
}

咱们设置的循环不变式：left指针之前的数组元素（不蕴含目前所指元素）不为val。

  • 初始 left 设为 0，即nums[0] 之前的元素不为 val，因为nums[0] 之前没有元素，left地位满足不变式要求。
  • 接下来的循环中，如果 nums[right] 不为 val，则将nums[right] 赋值给 nums[left] 后后移 left，完结本次循环。如果nums[right] 为val，则间接完结本次循环。每次循环，left地位均满足不变式要求。
  • 最终 right 指针遍历完数组元素后，完结整个循环，left地位满足不变式要求。

因而在循环完结后，left左侧元素均为非 val 元素，合乎算法要求。

复杂度剖析：

  • 工夫复杂度：O(n)，其中 n 为序列长度。每个地位至少被遍历两次。
  • 空间复杂度：O(1)。只须要常数的空间寄存若干变量。

优化：
咱们留神到，题目中还有一个阐明，“元素的程序能够扭转。你不须要思考数组中超出新长度前面的元素”，也就是说，咱们能够通过放弃原数组元素的地位不变来缩小赋值次数。
当 val 非常少的时候，原办法会呈现大量的冗余赋值，缩小赋值次数是对性能的一个大的晋升。

先贴代码：（GO 语言）

func removeElement(nums []int, val int) int {left, right := 0, len(nums)-1
   for right >= left {if nums[right] != val {nums[left], nums[right] = nums[right], nums[left]
         left++
      } else {right--}
   }
   return left
}

同样，咱们的循环不变量放弃不变，即 left 指针之前的数组元素（不蕴含目前所指元素）不为 val。设置数组首尾指针，循环终止条件为right >= left 以保障所有元素均被遍历过一次。循环中保护不变式，最终后果满足题目要求。

复杂度剖析：

  • 工夫复杂度：O(n)，其中 n 为序列长度。每个地位至少被遍历一次。
  • 空间复杂度：O(1)。只须要常数的空间寄存若干变量。
退出移动版