All values in my table are Numbers. How can I check to see if any of the values in the table are the same?
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.