arrays - 如何使我的 ruby​​ remove_duplicates(nums) 算法更高效

Question

这是编码挑战:给定一个排序数组，就地删除重复项，使每个元素只出现一次并返回新长度。

不要为另一个数组分配额外空间，您必须通过使用 O(1) 额外内存就地修改输入数组来执行此操作。

我的回答

def remove_duplicates(nums)

    hash = {}

    nums.each do |num|
      if hash[num].nil?
        hash[num] = 1
      end 
      if hash[num] = 1
        i = nums.index(num)
        nums.delete(num)
        nums.insert(i, num)
      end 
    end

    nums.length    
end

在 leetcode 上，我的答案通过了 160/161 个测试用例。但我收到“超出时间限制”错误。该错误表明我的回答不够有效，无法解决最后一个测试用例。

我是初学者，我正在寻找有关如何使我的回答更有效率的建议(在 ruby​​ 中)!

Answer 1

如果您不想使用评论中建议的内置方法之一，在 O(n) 时间和 O(1) 空间中执行此操作的一种算法是使用 2 个索引循环遍历大批。第一个将是您上次插入唯一值的索引，第二个是您当前正在查看的元素的索引。这样做的关键是 nums 数组是排序的，所以你只需要设置下一个值，如果它大于当前值。它不能小于(因为已排序)并且如果它等于您插入的最后一个值，则它不是唯一的。例如:

nums = [1, 1, 1, 2, 2, 3, 4, 5, 5, 5, 5, 5, 6, 7, 8, 8, 9, 10, 10]
def remove_duplicates(nums)
  return 0 if !nums || nums.empty?
  insertion_index = 0

  1.upto(nums.length - 1) do |lookup_index|
    if nums[lookup_index] > nums[insertion_index]
      insertion_index += 1

      nums[insertion_index] = nums[lookup_index]
    end
  end

  # nums is currently:
  # => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 5, 5, 6, 7, 8, 8, 9, 10, 10]
  insertion_index + 1
end

remove_duplicates(nums)

您的返回值将是 insertion_index + 1，因为 insertion_index 是插入最后一个唯一值的索引，所以数组的长度是最终索引 + 1。

自从我完成一个 leetcode 问题已经有一段时间了，但我似乎记得在这样的问题中，你需要在适当的位置调整数组的大小，只是把所有的东西都留在最后，不管是什么方法(我们在 Ruby 中，但有很多其他语言的提交，其中只调整数组大小并不容易)。如果您愿意/但如果您只需要唯一数组的长度，则可以随意从末尾删除值(根据说明就地删除)，则没有必要这样做。