Raised This Month: $ Target: $400
 0% 

How to get unique id from array


  
 
 
Thread Tools Display Modes
Prev Previous Post   Next Post Next
Mikka
Member
Join Date: Dec 2018
Old 05-27-2022 , 08:45   Re: How to get unique id from array
Reply With Quote #4

Your statements are too complicated for me

Quote:
Originally Posted by HamletEagle View Post
If you always have the ids in sorted order like in your example, then the solution can be done more efficiently(one pass over 2 or O(n) vs O(n^2)) compared to ARUKARI's solution.

PHP Code:
getUniqueElements(inputnumElementsoutput, &numUnique)
{
    new 
currentValue = -1;
    
    for(new 
0numElementsi++)
    {
        if(
arr[i] != currentValue)
        {
            if(
currentValue != -1)
            {
                
output[numUnique++] = currentValue;
            }
           
            
currentValue arr[i];
        }
    }
    
    
output[numUnique++] = currentValue;

My code doesn't change the original array, it extracts the data into a new one, but the solution can be modified to work in place. I leave this to you, as practice.
Note that I assumed your ids are >0. The code will not work correctly if some ids are -1. You also need to handle the case when the array is empty(just check before doing anything).

If the ids are not sorted, then you can still do it in only one pass(O(n)), by using a trie(assuming the trie implementation inside AMXX provides O(1) access on average). If it is a tree-based implementation, then likely it provides O(log(n)) access which results in an O(n * log(n)) overall complexity, which is still better than O(n^2).
Keep in mind that this matters only when the size of your array grows. If your array is small, then any solution will do just fine.

Below is the solution using a trie:

PHP Code:
getUniqueElements(inputnumElementsoutput, &numUnique)
{
    new 
Trie:set TrieCreate();
    new 
strKey[12];
    
    for(new 
0numElementsi++)
    {
        
num_to_str(input[i], strKeycharsmax(strKey));
        if(!
TrieKeyExists(setstrKey))
        {
            
output[numUnique++] = arr[i];
            
TriePushCell(setstrKey0);
        }
    }
    
    
TrieDestroy(set);

Here is how you can call either of these 2 functions:
PHP Code:
//assuming you have an array ids you want to process with numIds ids inside it

new uniqueIds[SIZE_HERE]
int numUnique;
getUniqueElements(idsnumIdsuniqueIdsnumUnique)

for(
int i 0numUniquei++)
{
    
//do something with uniqueIds[i]

Mikka is offline
 



Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -4. The time now is 21:19.


Powered by vBulletin®
Copyright ©2000 - 2024, vBulletin Solutions, Inc.
Theme made by Freecode