如何在不使用' uniq '方法的情况下查找数组中的重复项

Question

我正在做一个挑战，制作一个方法来查找数组中的重复值，并打印出一个没有重复值的新数组。Ruby有一个内置的uniq方法;但是，我不允许使用它。

在我看来，这应该是可行的:

def uniques(array) 
  tempPos = 0
  arrayPos = 0
  duplicate = true
  result = [] # array the result will be "pushed" too
  for arrayPos in 0..array.length
    for tempPos in 0..array.length
      # If the values at the indexes are the same. But the indexes are not the same.
      # we have a duplicate
      if array[arrayPos] == array[tempPos] && arrayPos != tempPos
        duplicate = true
      else
        duplicate = false
      end
      if duplicate == false
        result[arrayPos] = array[arrayPos]
      end
    end
    puts duplicate
  end
  puts result.inspect
end

输出:

uniq *this is the short hand user input to run the method*
false
false
false
false
false
false
[1, 2, 1, 4, 5, nil]

我一定是做错了什么

Answer 1

允许使用Set吗?

require 'set'
array = [1, 2, 3, 3, 3, 4]
Set.new(array).to_a
#=> [1, 2, 3, 4]

另一种方法是遍历数组中的每一对:

array.each_cons(2).with_object([array.first]) do |pair, result| 
  result << pair.last unless pair.first == pair.last 
end
#=> [1, 2, 3, 4]

Answer 2

有很多方法可以做到。这是另一个。假设:

arr = [3,5,1,3,4,1,1]

构造:

h = arr.group_by(&:itself)
  #=> {3=>[3, 3], 5=>[5], 1=>[1, 1, 1], 4=>[4]} 

重复项由:

h.select { |_,v| v.size > 1 }.keys
  #=> [3, 1]

和一个没有重复项的数组由:

给出:

h.keys
  #=> [3, 5, 1, 4] 

Answer 3

你的逻辑工作得很好，尽管上面提到的set会更好。您还可以对元素进行排序，然后找到具有相同值的相邻对，这不会像set那样工作，但会比您当前的解决方案稍微好一些:

修饰你现有的内容:

def uniques(array) 
  result = [] # array the result will be "pushed" too
  for arrayPos in 0...array.length
    duplicate = false
    for tempPos in 0...result.length
      # if the values at the indexes are the same... but the indexes are not the same...
      # we have a duplicate
      duplicate ||= (array[arrayPos] == result[tempPos])
    end
    if !duplicate
      result << array[arrayPos]
    end
  end
  puts result
end

一个稍微好一点的方法(尽管性能仍然很差):

def uniques(array) 
  result = [] # array the result will be "pushed" too
  for arrayPos in 0...array.length
    duplicate = result.include?(array[arrayPos])
    if !duplicate
      result << array[arrayPos]
    end
  end
  puts result
end

虽然这个解决方案对于学习任务来说是OK的，但你应该注意到它的复杂性是O(n^2) (n ^ 2)。这意味着对于大小为n的数组(例如n=10)，您要进行n平方(100)次迭代。

情况越来越糟。如果你有一个长度为1,000,000的数组，你将进行1,000,000,000,000次迭代。这就是为什么使用set是如此重要，它的平均运行时间要低得多。

Answer 4

一个相当简单的方法，所以这是利用array.include?

new = []
arr.each { |x| new << x unless new.include?(x)}
puts new

这将给你一个数组(new)，它只包含原始数组(arr)中的唯一元素

Answer 5

简单复制数组

arr1 = [1,3,4,5,6,6,6,1] 
arry = Array.new(arr1)
puts arry

使用OR操作符查找唯一数组的简便方法

arr1 = [1,3,4,5,6,6,6,1] 
arr2 = Array.new # creating new array
arry = arr1 | arr2 # compare two array using OR operator
puts arry