Scripting Helpers is winding down operations and is now read-only. More info→
Ad
Log in to vote
4

how do i remove all duplicates of a array?

Asked by 6 years ago
Edited 6 years ago

for example if i had this script:

function RAD()
    --remove duplicates code here
end
array = {1,2,2,3,3,44,56,67}
print(RAD())--outputs 1,2,3,44,56,67

is there any way i could do this i have tried multiple things but none of them worked

0
If you wanted my example to work with dictionaries or tables with holes (i.e. nil values), you would need to change ipairs to pairs, because ipairs only loops through arrays. User#25115 0 — 6y
0
I have included a better method that is more efficient in my answer due to the realization that my first method was not as efficient as the better one. User#25115 0 — 6y

2 answers

Log in to vote
5
Answered by 6 years ago
Edited 6 years ago

You would have to have a new array that you insert each element (that is not a duplicate of an element you have already inserted) into. Of course, for this to work, you would need to have a function that checks if something has already been added or not. This explanation is not that clear, unless you see an example:

local array = {1, 2, 3, 4, 5, 5, 1, 2} -- array with duplicates

local function inArray(arr, element) -- function to check if something is in an array
    for _, value in ipairs(arr) do -- ipairs is the recommended iterator for looping through arrays
        if value == element then
            return true
        end
    end
    return false -- if no element was found, return false
end

local function removeDuplicates(arr)
    local newArray = {} -- new array that will be arr, but without duplicates
    for _, element in ipairs(arr) do
        if not inArray(newArray, element) then -- making sure we had not added it yet to prevent duplicates
            table.insert(newArray, element) 
        end
    end
    return newArray -- returning the new, duplicate removed array
end
array = removeDuplicates(array)
for _, element in ipairs(array) do -- testing
    print(element)
end
-- output --> 1 2 3 4 5 

Edit: After talking to a few other people and reviewing the other answer, I realized that I had chosen the less efficient method for doing this. Because of that, I have decided to add the more efficient method into my answer so that people realize that it is the better way to go. Because of the way tables work in Lua, we can just have key (the element in our array) value (a boolean that says that it is already in our newArray) pairs that provide information on whether or not a particular element is a duplicate. Example:

local array = {1, 2, 3, 4, 5, 5, 1, 2}
local function removeDuplicates(arr)
    local newArray = {}
    local checkerTbl = {}
    for _, element in ipairs(arr) do
        if not checkerTbl[element] then -- if there is not yet a value at the index of element, then it will be nil, which will operate like false in an if statement
            checkerTbl[element] = true
            table.insert(newArray, element)
        end
    end
    return newArray
end

I hope these examples help. Have a great day scripting!

1
Or you could just sort the array and check for previous and current value and remove it accordingly. Zafirua 1348 — 6y
0
Yes, but that would not work if the elements were not numerical. How would you sort in that scenario? User#25115 0 — 6y
0
You can provide a custom comparator function in table.sort. https://www.lua.org/pil/19.3.html fredfishy 833 — 6y
0
A comparator function is basically a function the sorting algorithm uses to compare two values. It takes two arguments: a and b. It returns true if a is considered "less than" b. fredfishy 833 — 6y
View all comments (4 more)
0
I know what a comparator function is. User#25115 0 — 6y
0
ok but somebody else might not - answers aren't written solely for the benefit of one person fredfishy 833 — 6y
0
I see what you mean. I thought you were talking solely to me and Zafirua. User#25115 0 — 6y
0
My bad. User#25115 0 — 6y
Ad
Log in to vote
3
Answered by
fredfishy 833 Moderation Voter
6 years ago
Edited 6 years ago

The best performance you're going to get is building a hash set alongside the new table.


function removeDuplicates(tab) hashSet = {} new = {} for index, value in tab if hashSet[value] ~= nil then -- Duplicate else table.insert(new, value) hashSet[value] = true end end end

Doing a linear search for an element in a list normally is O(n). If you're doing that for every element in a list, then you've got O(n^2), which is pretty bad.

Sorting a list is O(n log n), which is much better than O(n^2) but can still get pretty expensive.

On the other hand, checking if an element is in a hash set is an O(1) operation, meaning that the "remove duplicates" function can perform in O(n * 1) = O(n).

0
Ingenious solution. I had not thought of this as a more efficient method. User#25115 0 — 6y
0
This should be the accepted answer tbh Amiaa16 3227 — 6y
0
You forgot a do in your for loop and ~= nil is redundant. User#25115 0 — 6y

Answer this question