wu :: forums « wu :: forums - Array Problem (count a[i]<=a[j], i>=j) » Welcome, Guest. Please Login or Register. Nov 24th, 2024, 4:05am

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    cs (Moderators: william wu, ThudnBlunder, Icarus, SMQ, Grimbal, towr, Eigenray)    Array Problem (count a[i]<=a[j], i>=j) « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: Array Problem (count a[i]<=a[j], i>=j)  (Read 974 times) witee Newbie     Posts: 48 Array Problem (count a[i]<=a[j], i>=j)   « on: Jul 18th, 2010, 5:00am » Quote Modify Given an array for each index (j) find the number of numbers less then and equal to a[j] from j to n.. complexity < 0(n*n) « Last Edit: Jul 18th, 2010, 2:15pm by Grimbal » IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Array Problem   « Reply #1 on: Jul 18th, 2010, 6:29am » Quote Modify Use a binary search tree, and for each node keep track of the number of nodes in its subtree. IP Logged Wikipedia, Google, Mathworld, Integer sequence DB witee Newbie     Posts: 48 Re: Array Problem   « Reply #2 on: Jul 18th, 2010, 11:43am » Quote Modify check for this input   2 3 1  this method will give 0 for 2nd array element while the ans. is 1 .correct me if i m wrong!!!! IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Array Problem   « Reply #3 on: Jul 18th, 2010, 12:11pm » Quote Modify Perhaps I should add you ought to start at the back of the array. It's the natural place to start, since you want information about elements following a given one, and you'll only have such information if you looked there first. So first you have an empty BST, which contains 0 elements less or equal to 1. Then you insert the 1, at which point it contain one element less than or equal to 3. Then you insert the 3, and it contains one element less than or equal to 2. So you get 1,1,0 (in order of input, in reverse order of finding them). IP Logged Wikipedia, Google, Mathworld, Integer sequence DB witee Newbie     Posts: 48 Re: Array Problem   « Reply #4 on: Jul 18th, 2010, 12:23pm » Quote Modify The worst case complexity is 0(n*n) when elements r sorted in decreasing order..correct me if i m wrong! IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Array Problem   « Reply #5 on: Jul 18th, 2010, 1:19pm » Quote Modify Insertion into a bst is an O(log n) operation is you implement the BST properly (with automatic balancing). So it's O(n log n) in total. IP Logged Wikipedia, Google, Mathworld, Integer sequence DB birbal Full Member     Gender: Posts: 250 Re: Array Problem   « Reply #6 on: Jul 24th, 2010, 9:06am » Quote Modify on Jul 18th, 2010, 12:23pm, witee wrote: The worst case complexity is 0(n*n) when elements r sorted in decreasing order..correct me if i m wrong! Well not always. After each insert, you can check and balance the tree. http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree IP Logged The only thing we have to fear is fear itself! Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board