首页 > 其他 > 详细

Leetcode1299. Replace Elements with Greatest Element on Right Side

时间:2020-01-17 23:31:10      阅读:64      评论:0      收藏:0      [点我收藏+]

public int[] replaceElements(int[] arr) {
for(int i=0;i<arr.length-1;i++)
arr[i]=findRightmax(i,arr);
arr[arr.length-1]=-1;
return arr;
}
public int findRightmax(int flag,int []nums){
int max=nums[flag+1];
for(int i=flag+1;i<nums.length;i++)
if(max<=nums[i]){
max=nums[i];
}
return max;
}

我的代码是不断去右边寻找最大值

这其中会有很多工作是重复的

Explanation

Iterate from the back to the start,
We initilize mx = 1, where mx represent the max on the right.
Each round, we set A[i] = mx, where mx is its mas on the right.
Also we update mx = max(mx, A[i]), where A[i] is its original value.

Complexity

Time O(N)

public int[] replaceElements(int[] A) {
        for (int i = A.length - 1, mx = -1; i >= 0; --i)
            mx = Math.max(A[i], A[i] = mx);//mx是A[i]右侧最大值,故每开始新的循环的时候,将当前值和后面的最大值比较,从而更新最大值,同时完成A[i]=mx,将当前值更新为后面最大值的操作
        return A;
    }

Leetcode1299. Replace Elements with Greatest Element on Right Side

原文:https://www.cnblogs.com/chengxian/p/12207602.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!