My c++ solution with multiset O(nlgk)


  • 0
    T
    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            //using set
            vector<int>ret;
            multiset<int>s;
            for(int i=0;i<nums.size();i++){
                if(i<k){
                    s.insert(-nums[i]);
                }
                if(i>=k-1){
                    if(i!=k-1){
                        s.insert(-nums[i]);
                        s.erase(s.find(-nums[i-k]));
                    }
                     ret.push_back(-(*s.begin()));
                }
            }
            return ret;
        }
    };

  • -2
    F

    It should be done in O(n) not O(nlogk) where k is potentially as large as n.


  • 0
    M

    That's only a follow-up question.


  • 0
    F

    If your algorithm doesn't have the highest performance, your algorithm isn't right. Calculating out the results means nothing. You can always get the result using brute force. No challenge there at all if people just use naive solutions like this.


  • 0
    M

    You're wrong. In general, and here in particular, as the follow-up question wouldn't make sense if you were expected to produce highest performance right away. Also, keep in mind that this site is about interviews, where achieving highest performance isn't even possible all the time, due to the limited amount of time you have. Finally, your " You can always get the result using brute force" is also wrong, as often the test cases are too large for that or the problem does request certain better efficiency.


  • 0
    F

    You are completely wrong about all you said.
    First of all, this problem is marked as Hard. A O(nlgK) solution is really a no brainer.
    Second, before you comment on what I said: " You can always get the result using brute force", please read it 5 times before you say anything. I said "GET THE RESULT", get the result doesn't mean it's a right algorithm, and it doesn't mean it has to pass the test cases, just same as passing all test cases doesn't mean it's a correct solution. If you claim O(nlogK) is a right solution, I could claim O(n^2) is also right, because it also can generate the right results. If you say O(n^2) isn't efficient, I can also say O(nlogK) isn't efficient.


  • 0
    M

    No, you're wrong. I don't know why it's marked as hard, I find these labels a bit arbitrary. But even if that indicated anything in your direction, surely it wouldn't overrule the explicitly given and quite clear follow-up question right on the problem page that you so conveniently keep ignoring.

    If it doesn't pass the test cases then it doesn't get the result. I don't know what O(n^2) solution you have in mind, but as a test I just added

        int n = nums.size(), sum = 0;
        for (int i=0; i<n; ++i)
            for (int j=0; j<n; ++j)
                sum += nums[j];
    

    to a fast O(n) solution and then the solution didn't get the result anymore, as it was stopped before it had the result.

    Or try the Count Complete Tree Nodes problem. I very highly doubt you can get the result with a brute force solution.

    "If you claim O(nlogK) is a right solution, I could claim O(n^2) is also right,"

    If it gives the correct answer and fulfills all other requirements then yes, I'd say it's right.

    "If you say O(n^2) isn't efficient, I can also say O(nlogK) isn't efficient."

    Absolutely. That's not what you're saying, though. You don't say it isn't efficient, you say it isn't right. And that's not right.

    "Calculating out the results means nothing."

    No. Doing it less efficiently is worth less (unless it makes up for it with other qualities), but it's not worthless.


  • 0
    M

    Btw, I see you posted a program that takes O(n) space rather than O(1) space. Better quickly delete that, as it's not right, yes? That problem is also labeled "hard" and asks for O(1) even as a "note" rather than as "follow up".


  • 0
    F
    This post is deleted!

  • 0
    F

    And about this comment:
    "Btw, I see you posted a program that takes O(n) space rather than O(1) space. Better quickly delete that, as it's not right, yes?"
    what the hell are you talking about????????????!!!!!!!!!??????????? You are so ridiculous!
    1st of all, you are referring to another problem, which is totally unrelated to this problem.
    2nd, my solution to that problem literally only takes O(1) space (despite the space required by recursive traversal), do you know even know how to properly evaluate the complexity??


  • 0
    M

    "Still, same logic, if you say your stupid O(nlgK) solution is right, I can also say a O(n^2) solution is right."

    Um... yes... I already agreed to that.

    (Under the condition that it fulfills all requirements, which of course also applies to O(nlgK) and O(n) solutions).

    "You say O(n^2) solution isn't efficient, I can say your stupid O(nlgK) solution isn't right."

    Um... "efficient" and "right" aren't spelled differently just for fun. They actually do mean different things. But the direction is wrong anyway.

    "Btw, why do you log on using a different ID and argue with people when people downvote your solution??"

    User third_round is not my account, I don't even know who that is. Grasping at straws much?

    "You are ridiculous and speak like a clown."

    Excellent intelligent argument.

    "another problem, which is totally unrelated to this problem."

    It is related because it's the same situation, to which your general statement applies. What is your problem?

    "my solution to that problem literally only takes O(1) space (despite the space required by recursive traversal)"

    No, the recursion is what makes it O(n) space.


  • 0
    F
    This post is deleted!

  • 0
    F

    You are just a clown and why this is an excellent intelligent argument. Let me explain it to you:

    First of all, you don't understand what is "get a result" and what is a "efficient" algorithm. You can always get the result using brutal force, no matter how long it takes, 1billion year or 2^2^2...^n years. It can give you a result eventually. Is it efficient? of course it isn't. So if you think "get a result" == correct solution, the brute force solution will be as good as your O(nlogK) solution. if you think "isn't efficient" == "wrong solution" then your O(nlogK) solution is as wrong as the brute forece one. Is it clear? You don't understand this, you are as dumb as a clown.

    You searched through my profile to find anything that isn't perfect and post it here to argu about. Don't you think this behavior is as ridulous as a clown? That problem is totally unrelated to this problem. Whether I did it right or I simply submitted a "cout<<YOU ARE DUMB" has no effect on the arguments here. What you did and talked about doesn't make any sense.

    Though it is totally unrelated here, lets talk about that solution. That solution uses a recursion, that all other solutions posted used. But fine, it is not a real O(1) space Solution, I agree. So I just post another soltuion(https://leetcode.com/discuss/48196/real-o-1-space-no-recursion-no-stack-etc-o-time-solution-48ms-c), which is real O(1) space, now can you shut up clown?


  • 0
    M

    So much stubborn stupidity and misrepresentation and hostility... not going to bother with you further. Kudos for the Morris traversal, though, if that's yours.


  • 0
    F

    You just said the word "fucker", not me. Clown is not a F word. So you are the "much stubborn stupidity and misrepresentation and hostility" Now you completely lose this argument with me, you are mad? lol.
    You just showed how you are ridiculous again:
    "Morris traversal, though, if that's yours."
    lmao, so, BST, quick sort and almost everything you know weren't invented by yourself, please DON'T use them, because they are not yours. You see how ridiculous your logic is????
    Oh, C++ wasn't invented by you either, you don't own C++, so don't use C++ any more, rolf. Oh, you don't own earth either, earth isn't yours, so don't use earth, hmm, better die now so you don't waste the resources on the earth.

    And you see why I'm superior to you? When you pointed out a problem, though very unreasonable, what I did was to develop a new algorithm and solve the problem perfectly to make you shut up (and you did now). What's your reaction to people who pointed out a legit problem of your solution? argue, argue again, insult the person, search through the person's profile to find any place that you can find a tiny problem.

    Compare them by yourselves, now you see why you are a clown and why I was like a king? I correct it to make you shut up, you just cry, find excuse, find other's problem. What a pathetic clown


  • 0
    F

    You just said the word "fucker", not me. Clown is not a F word. So you are the "much stubborn stupidity and misrepresentation and hostility" Now you completely lose this argument with me, you are mad? lol.
    You just showed how you are ridiculous again:
    "Morris traversal, though, if that's yours."
    lmao, so, BST, quick sort and almost everything you know weren't invented by yourself, please DON'T use them, because they are not yours. You see how ridiculous your logic is????
    Oh, C++ wasn't invented by you either, you don't own C++, so don't use C++ any more, rolf. Oh, you don't own earth either, earth isn't yours, so don't use earth, hmm, better die now so you don't waste the resources on the earth.

    And you see why I'm superior to you? When you pointed out a problem, though very unreasonable, what I did was to develop a new algorithm and solve the problem perfectly to make you shut up (and you did now). What's your reaction to people who pointed out a legit problem of your solution? argue, argue again, insult the person, search through the person's profile to find any place that you can find a tiny problem.

    Compare them by yourselves, now you see why you are a clown and why I was like a king? I correct it to make you shut up, you just cry, find excuse, find other's problem. What a pathetic clown


  • 0
    M

    You just said the word "fucker"

    Just for the record: That's a total lie. I didn't say that or anything like it.

    Not going to bother with the rest, just really couldn't let that one stand.


  • 0
    F

    Completely a loser. Why run away when you are proved completely wrong? Now you know you should shut up? Pathetic clown.


  • 0
    I

    @ManuelP: Your comments are valuable and useful. Thank you! Let's not waste time on those who may just be in a bad mood and want to argue with someone for no reason.
    @third_round: Your code is correct and should be a solid answer if this question is asked in an interview.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.