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
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
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)
.