algorithm - Array remove duplicate elements -

-

I have an unreserved array, if present, what is the best way to remove all duplicates of an element?

Example: 

  one [1,5,2,6,8,9,1,1,10,3,2,4,1,3,11 , 3]

So the array should look after that operation 

  one [1,5,2,6,8,9,10,3 , 4,11]

Check each element against each other element

The simple solution is to check each element against every other element. It is useless and produces o (n 2 ) solution, even if you only "Forward".

Sort again delete the duplicate

The best solution is to sort the array and then check each element next to it to find duplicates. Select an efficient type and it's O (n log n).

There is no insecurity order with a sort-based solution. An additional step can take care of this. Place all entries (in unique sorted array) in the hashtable, which has O (1) access. Then iterate over the original array. For each element, check whether it is in the hash table. If so, add it to the result and remove it from the hash table. You will end with a resultant array, in which each element will be placed in the same position as its first event in the order of origin.

Linear type of integer

If you can do better by using the Radix sort to deal with the integers of certain boundaries, if you believe that the number 0 to 1,000,000 Between, for example, you can allocate a little vector of some 1,000,001. For each element in the original element, you set the corresponding bit based on its value (such as the value of 13 results in setting 14th bits). Then cross the original array, check whether it is in bit vector or not. If so, add it to the result array and clear that bit with a bit vector. It is O (n) and does trade of space for time.

hash table solution

Which takes us to the best solution: Sorting is actually a distraction, though useful (1) Create a hashtable with access to the original list If it is not already in the hashtable, add it to the result array and add it to the hash table. If it is in the hash table, ignore it.

This is the best solution, why else? Because such problems are about problems that you have (or should) have about the knowledge and are about to refine them based on the solutions that you do in the solution, develop a solution and its Understanding the thinking behind is much more useful than a solution solution.

In addition to this, hash tables are not always available. Take an embedded system or some space where the space is very limited. You can apply a quick sort to a handful of epododes, which is much less than any hash table.


Comments

Post a Comment

Popular posts from this blog

c# - sqlDecimal to decimal clr stored procedure Unable to cast object of type 'System.Data.SqlTypes.SqlDecimal' to type 'System.IConvertible' -

-
I'm new to this I'm writing a clr. stored procedure that can be used to get values ​​used in a calculation Call for another stored procedure for Gives an archived methodology int (I think SqlInt32? Value of the table's value is int) which is then necessary to convert to decimal. Here I have the code: Public static integral mood (SQL MDMMYLUE, escalistering AMY type, out of SQLDCM Result) {aResult = 0; Try {SqlConnection conn = New SqlConnection ("Reference Connection = True"); SqlCommand cmd = New SqlCommand ("sp_GetType", conn); Cmd.Parameters.AddWithValue ("@ myValueType", aMyValueType); Cmd.CommandType = CommandType.StoredProcedure; Conn.Open (); Object type = CMD. Exclamation Asser (); Conn.Close (); Decimal type FORCalculation = Convert. ToDecimal (type); Decimal value = convert toDecimal (aMyValue); // ** calculation calc = new calculation (); Decimal result = calorie.docalulation (typefarculation, value); I get an exception...
Read more

Calling GetGUIThreadInfo from Outlook VBA -

-
I need to find the active window'm writing a VBA macro in MS Outlook, which is a specific process. The goal of this is to get the active window / document name even if its original application has more than one document interface. User processor with GetCurrentThreadId is active, I am using GetGUIThreadInfo to get .dll. Here is the correct code: private type RECT as as Left LongPtr top LongPtr right LongPtr down LongPtr termination of private type GUITHREADINFO cbSize as LongPtr flags LongPtr hwndActive LongPtr hwndFocus LongPtr hwndCapture LongPtr as as as as as reset as LongPtr rcCaret as LongPtr hwndCreate as LongPtr hwndMoveSize as HwndMenuOwner end of Private Equity PtrSafe function GetWindowThreadProcessId Lib "user32" (_BVV hnw LongPtr as LongPtr Nig Mr. announced as PtrSafe function GetGUIThreadInfo Lib "user32" _ (ByVal dwthreadid as LongPtr, _ lpguithreadinfo as GUITHREADINFO) LongPtr Sub MyFunction () as dim strWindowTitle string = space as s...
Read more

Obfuscating Python code? -

-
I'm looking for a way to hide my Python source code. print "Hello World!" How can I encode this example so that it is not human-readable? I have been asked to use Base 64 but I'm not sure how. itemprop = "text"> It is limited only, first level ambiguous resolution, but has built-in: byte-code in Python Is a compiler for: dragon-o-m py_compile & lt; Your program.py & gt; creates a .pyo file with a byte-code, and where the docstrings are removed, etc. You can rename .pyo with the .py extension, and python & lt; Your program.py & gt; runs as your program, but it does not have your source code. PS : If your program blur modules like this, you need to rename them with the .pyc suffix (I Not sure it will not break a day), or you can work with .pyo and run them with python -o ... .pyo ( Import should work). This will allow dragon to search your modules (otherwise, Python looks for the .py module).
Read more