All values in my table are Numbers. How can I check to see if any of the values in the table are the same?
✓ ANSWER ACCEPTED
How do I check if any of the values in a table are the same?
2 answers
✓ Accepted answer
There are more or less 3 different ways to do this.
Each basically consider each element and check whether or not that element has been seen before / is in the table multiple times (by looking for it).
The most straightforward way is to check all of the remaining elements and compare them to the current one. For example,
for i = 1, #list do
local element = list[i]
-- Search for `element` in the
-- remainder (from i + 1 on) of the list
for j = i + 1, #list do
-- For each element in the remainder of the list...
if list[j] == element then
-- list[i] and list[j] are the same!
end
end
end
If there are N elements in the table, then this takes approximately N * N / 2 checks (a quadratic time). This can be very slow if you have a large list.
We can go faster, though! If we sort the list (if somehow the data can be sorted -- this can no longer be done in general), then we can just compare adjacent indices.
That would make this take approximately N * log(n) + N checks, which is significantly better than the quadratic implementation above.
One efficiency note: If you cannot modify the original table for some reason, you will first have to copy it, taking N extra memory (which the 1st implementation doesn't have a problem with). Of course, Lua is not usually a language where you have to care about memory consumption.
For numbers (or strings), we can use the default table.sort; for other data types, we would have to define our own.
-- First, sort it.
table.sort( list )
for i = 1, #list - 1 do
-- If they are the same, then, since they're sorted
-- they will be right next to each other.
-- So we just compare adjacent values.
if list[i] == list[i + 1] then
-- list[i] and list[i + 1] are the same!
end
end
Finally, we can go much faster! In fact, just N time, by using a hashtable. This, however, takes significantly more memory -- though, again, Lua isn't a context where memory usage is very important.
-- Use a hashtable:
haveSeen = {}
for i = 1, #list do
local element = list[i]
-- Check whether or not any previous place has
-- recorded `element` into `haveSeen`
if not haveSeen[element] then
-- haveSeen[element] is empty
haveSeen[element] = i
else
-- haveSeen[element] is NOT empty --
-- the element has already been seen
-- list[ haveSeen[element] ] and list[i] are the same!
end
This should work, just tested.
nums = {1,2,3,4,4} --Example, replace this with your table
function TableCheck(tab,val,position) --Create a function with the input arguments
for i = 1, #tab do --Numeric for loop through 1 and the number of items in the table.
if tab[i] == val and position ~= i then --Makes sure tab[i] equals the value and that the position of the value is not the same as i.
return true --Returns true and stops the function
end
end
return false --Returns false if nothing is found.
end
for i = 1, #nums do --Numeric for loop through 1 and the number of items in the nums table.
local result = TableCheck(nums,nums[i],i) --Calls function with the arguments being the nums table, the value in the position of i in the nums table and i itself.
if result == true then --If the function returns true then.
print("Match found at table position " .. i) --Prints that a match was found at i.
break --Breaks loop.
else --If the function returns false then.
print("Match not found at table position " .. i) --Prints that a match wasn't found at i, and keeps searching if i isn't equal to #nums.
end
end
NOTE: You can get rid of the break below the match found print if you want to keep searching after finding a duplicate. You can also edit what happens after the result returns true or false, for example, you can make it remove the duplicate value when it's found.
This discussion is preserved as it was. New answers, comments, and votes are closed.
1 comment
This is quadratic - very slow.