StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>By assuming multiplication and division is O(1):</p> <p>Think about numbers, you can write them as:</p> <p><strong>Number(i) = A0 * n^765 + A1 * n^764 + .... + A764 * n + A765.</strong></p> <p>for coding number to this format, you should just do Number / n^i, Number % n^i, if you precompute, n^1, n^2, n^3, ... it can be done in O(n * 765)=> O(n) for all numbers. precomputation of n^i, can be done in O(i) since <code>i</code> at most is 765 it's O(1) for all items. </p> <p>Now you can write Numbers(i) as array: Nembers(i) = (A0, A1, ..., A765) and know you can radix sort items :</p> <p>first compare all A765, then ...., All of Ai's are in the range 0..n so for comparing Ai's you can use <a href="http://en.wikipedia.org/wiki/Counting_sort" rel="nofollow">Counting sort</a> (Counting sort is O(n)), so your radix sort is O(n * 765) which is O(n).</p> <p>After radix sort you have two sorted array and you can simply find one similar item in O(n) or use <a href="http://en.wikipedia.org/wiki/Merge_algorithm" rel="nofollow">merge algorithm</a> (like merge sort) to find most possible similarity (not just one).</p> <p>for generalization if the size of input items is O(n^C) it can be sorted in O(n) (C is fix number). but because the overhead of this way of sortings are big, prefer to using quicksort and similar algorithms. Simple sample of this question can be found in <a href="http://en.wikipedia.org/wiki/Introduction_to_Algorithms" rel="nofollow">Introduction to Algorithm</a> book, which asks if the numbers are in range (0..n^2) how to sort them in O(n).</p> <p><strong>Edit:</strong> for clarifying how you can find similar items in 2-sorted lists:</p> <p>You have 2 sorted list, for example in merge sort how do you can merge two sorted list to one list? you will move from start of list 1, and list 2, and move your head pointer of list1 while head(list(1)) > head(list(2)), and after that do this for list2 and ..., so if there is a similar item your algorithm will stop (before reach the end of lists), or in the end of two lists your algorithm will stop.</p> <p>it's as easy as bellow:</p> <pre><code>public int FindSimilarityInSortedLists(List<int> list1, List<int> list2) { int i = 0; int j = 0; while (i < list1.Count && j < list2.Count) { if (list1[i] == list2[j]) return list1[i]; if (list1[i] < list2[j]) i++; else j++; } return -1; // not found } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

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