StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
18605160
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
1
CommunityOwnedDate
CreationDate
2013-09-04T03:57:45.710
FavoriteCount
0
LastActivityDate
2013-09-04T04:20:23.343
LastEditDate
2013-09-04T04:20:23.343
LastEditorUserId
1569108
OwnerUserId
1569108
ParentId
18604890
PostTypeId
2
Score
2
ViewCount
0
LastEditorDisplayName
text
Body
Sorting the array will cost you O(n log n) time. You can do it in O(n) time using k-selection. <ol> <li>Compute an array B, where B[i] = abs(A[i] - val). Then your problem is equivalent to finding the k values farthest from zero in B. Since each B[i] >= 0, this is equivalent to finding the k largest elements in B.</li> <li>Run k-selection on B looking for the (n - k)th element. See <a href="http://en.wikipedia.org/wiki/Quickselect" rel="nofollow">Quickselect</a> on Wikipedia for an O(n) expected time algorithm.</li> <li>After k-selection is complete, B[n - k] through B[n - 1] contain the largest elements in B. With proper bookkeeping, you can link back to the elements in A that correspond to them (see pseudocode below).</li> </ol> Time complexity: O(n) time for #1, O(n) time for #2, and O(k) time for #3 => a total time complexity of <code>O(n)</code>. (Quickselect runs in O(n) expected time, and there exist complicated worst-case linear time selection algorithms). Space complexity: <code>O(n)</code>. Pseudocode: <pre><code>farthest_from(k, val, A): let n = A.length # Compute B. Elements are objects to # keep track of the original element in A. let B = array[0 .. n - 1] for i between 0 and n - 1: B[i] = { value: abs(A[i] - val) index: i } # k_selection should know to compare # elements in B by their "value"; # e.g., each B[i] could be java.lang.Comparable. k_selection(n - k - 1, B) # Use the top elements in B to link back to A. # Return the result. let C = array[0 .. k - 1] for i between 0 and k - 1: C[i] = A[B[n - k + i].index] return C </code></pre>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POReturn the k elements of an array farthest from val
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USMihai Danila
UserOwnerUserId
1. USMihai Danila
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId
1. COThanks! I'm looking through it right now. I will get back to you later.
 singulars
 PostPostId
 PO
 UserUserId
 UScatchwisdom

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.