Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The solution depends on your requirement. If you have a small array size <em>(n&lt;10^6)</em>, scanning through the array on every insertion would suffice, but if you have a large array and frequent insertions, I would propose a different solution.</p> <p>Scanning through an array on every insertion would require a complexity of <strong>O(n)</strong>. For small numbers, the overhead is ignorable, but as the size of array increases, traversal on every insertion is inefficient.</p> <p>If you need performance and if memory is not your constraint, you can take a boolean array and initialize all elements to <strong>false</strong>. Then whenever you get a number, make its index value in the boolean array to <strong>true</strong>, And while inserting, check whether the boolean value at the index number of the element being inserted.</p> <p>Here is the code to initialize the boolean array (initializing it would make all elements false):</p> <pre><code>boolean [] duplicateValuesArray = new boolean[Integer.MAX_VALUE]; </code></pre> <p>Here is the function which inserts an element in the array:</p> <pre><code> public void insertElement(int elementToBeInserted) { if(!duplicateValuesArray[elementToBeInserted]) //check if element already in array duplicateValuesArray[elementToBeInserted] = true; mainArray[index++] = elementToBeInserted; } </code></pre> <p>In this way, whenever you get a number, value for that index in the boolean array is set to <strong>true</strong>, and while insertion, everytime the index is checked, if value is <strong>true</strong>, that element exists in the array, do not insert it.</p> <p>The complexity for this is much lower if you have a large <strong>mainArray</strong> <em>(n>10^6)</em> and you have frequent insertions. This is because, initializing a boolean array is one time <strong>O(n)</strong> complexity, and after that, checking for the element in the boolean array and insertion of element is just <strong>O(1)</strong> operation, happens in constant time. </p> <p>Thus effective complexity is reduced to just initializing the boolean array. And even in terms of memory footprint, I wouldn't mind because a boolean primitive just occupies one bit in the memory.</p> <p>P.S: Basically it is a memory vs performance trade off, and this is the Universal Computing Trade off, found everywhere.</p>
    singulars
    1. This table or related slice is empty.
    1. POAvoiding duplicate integers in an integer array
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USDhwaneet Bhatt
    1. USDhwaneet Bhatt
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTApproveEditSuggestion
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO+1 for exploring complexity and performance in this case
      singulars
      1. PO
      1. USPriyank Doshi
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload