A Solution using GREEDY, But is it REALLY o(n)?


  • 3
    J

    The ideas is simple ,using some greedy tactics.

    We generally maintain a start position to indicate the current position,and there are only 2 main steps for solving the problem.

    step(1): When you are at position start, you can go to positon start + 1 to start + nums[start] if nums[start] > 0, and now you can know
    whether you can go to the end by judging nums[start] >= nums.size()-1.If so, go to step(3). If not, go to step(2).

    step(2): From start + 1 to start + nums[start], in these nums[start] positions,pick one to be the next start position. And the rule for picking is simple:

    You pick a position start + i, from which you can move forward the longest distance,which means
    i + nums[start + i] >= j + nums[start + j] for any 1 <= j <= nums[start].

    So the start position is at start + i now. Then you go to the step(1).

    step(3): Return the answer.

    Finished! But I still have some questions about this solution, what is its time complexity? Is it really o(n)?

    class Solution {
            public:
                int jump(vector<int>& nums) {
                    if(nums.size() < 2)
                        return 0;
                    for(int start = 0, step = 1; ; step++){
                        if(start + nums[start] >= nums.size() - 1)
                            return step;
                     /* if(nums[start] == 0)
                            return false;  // doesn't need this for this problem's tests */
                        int maxDistence = 0, nextStart = start;
                        for(int i = 1; i <= nums[start]; i++){
                            if(i + nums[start + i] >= maxDistence){
                                nextStart = start + i;
                                maxDistence = i + nums[start + i];
                            }
                        }
                        start = nextStart;
                    }
                }
        };

  • 0
    S
    public class Solution {
    public int jump(int[] nums) {
        int maximum = 0;
        int nextMaximum = 0;
        int count = 0;
        
    	for (int i = 0; i < nums.length-1; i++) {
    		nextMaximum = Math.max(nextMaximum,nums[i]+i);
    		if (i == maximum) {
    			count ++;
    			if (nextMaximum >= nums.length-1) {
    				return count;
    			}
    			maximum = nextMaximum;
    		}
    	}
    	return count;
    }
    

    }


Log in to reply
 

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