stack - Data structure that deletes all elements of a set less than or equal to x in O(1) time -

-

i self studying algorithms course, , trying solve following problem:

describe data structure store set of real numbers, can perform each of following operations in o(1) amortized time:

insert(x) : deletes elements not greater x, , adds x set.
findmin() : find minimum value of set.

i realize findmin kind of becomes trivial once have insert, , see how linked list implementation, delete multiple elements simultaneously (ie o(1)), finding out link delete (aka x goes) seems o(n) or o(log n) operation, not o(1). problem gave hint: consider using stack, don't see how helpful.

any appreciated.

the original question below:

original problem

note goal o(1) amortized time, not o(1) time. means can work you'd per operation long n operations don't take more o(n) time.

here's simple solution. store elements in stack in ascending order. insert element, keep popping stack until it's empty or until top element greater x, push x onto stack. find-min, read top of stack.

find-min runs in time o(1). let @ insert. intuitively, each element pushed , popped @ once, can spread work of expensive insert across cheaper inserts. more formally, let potential n, number of elements on stack. each time insert, you'll number of pops (say, k) , potential increases 1 - k (one new element added, k removed). amortized cost k + 1 + 1 - k, 2. therefore, insert amortized o(1).

hope helps!


Comments

Post a Comment

Popular posts from this blog

php - render data via PDO::FETCH_FUNC vs loop -

-
i've been using 2 methods render data. the first one: function name($id,$name){ return '<div id="'.$id.'">'.$name.'</div>'; } echo implode($pdo->query("select id,name user")->fetchall(pdo::fetch_func,'name')); the second one: $users = $pdo->query("select id,name user")->fetchall(pdo::fetch_obj); foreach($users $user){ echo name($user->id,$user->name); } i don't understand how pdo::fetch_func works. tried figure out. however, not well-documented. could please explain fetch mode? , also, 1 performs better? thank you. both methods wrong , have learn how use templates , how separate business logic presentation logic. $users = $pdo->query("select id,name user")->fetchall(pdo::fetch_obj); tpl::assign('users', $users); is code business logic part. then in template <?php foreach $users $row): ?> <div id="<?=$...
Read more

c++ - OpenCV Error: Assertion failed <scn == 3 ::scn == 4> in unknown function, -

-
i read alot other solution still confused should mine... #include <opencv2/objdetect/objdetect.hpp> #include <opencv2/highgui/highgui.hpp> #include <opencv2/imgproc/imgproc.hpp> #include <iostream> #include <stdio.h> using namespace std; using namespace cv; int main(int argc, const char** argv) { //create cascade classifier object used face detection cascadeclassifier face_cascade; //use haarcascade_frontalface_alt.xml library face_cascade.load("haarcascade_frontalface_alt.xml"); //setup video capture device , link first capture device videocapture capturedevice; capturedevice.open(0); //setup image files used in capture process mat captureframe; mat grayscaleframe; //create window present results namedwindow("outputcapture", 1); //create loop capture , find faces while (true) { //capture new image frame capturedevice >> captureframe; ...
Read more

The canvas has been tainted by cross-origin data in chrome only -

-
uncaught securityerror: failed execute 'getimagedata' on 'canvasrenderingcontext2d': canvas has been tainted cross-origin data i getting above error in chrome. code(following) works fine in mozilla. have not corss domain issue. why above error in chrome? var wheel_canvas, wheel_context, can_w, can_h, wheel_grd; var large_radius = 160; var small_radius = 120; var wheel_canvas = document.getelementbyid('wheel_canvas'); var wheel_context = wheel_canvas.getcontext('2d'); var can_w = $(wheel_canvas).width(); var can_h = $(wheel_canvas).height(); var centerx = can_w / 2, centery = can_h / 2; var wheel_grd = null; test('#ff0000'); function test(hex) { $('#clrpicker').css({'left': 210, 'top': 210 }); inverted = hexbw(hex); $('#color_val_show').val(hex); current_color_hex_val_selected = hex; $('#color_val_show').css({'color':inverted,'background':hex}); fillgradient...
Read more