java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846 |
---|
文章来源:https://www.toymoban.com/news/detail-822615.html
解题思路 |
---|
- 题目要求我们返回一个数组长度为n的数组,必须含有1~n的所有数,并且从左到右,相邻的元素依次相减,它们的差,必须有k个不同的。比如1,2,3,4,5 这5个数两两相减,都只有一个差----1.如果想要两个不同的差,就不能这么摆。可以这样1,2,3,5,4 这样就有2-1 = 1. 5-3 = 2这样两个不同的差。
- 而且我们发现,想要有k个不同的差,必须至少有k+1个数才能完成。大家可以尝试1~5这5个数都只能用一次,然后组出相邻相减情况下的6个不同的差,是不行的。
- 最简单的做法就是,用最后一个-最前面的,然后依次缩小范围(用过的不再使用),再次用后面的-前面的。直到达到目标要求的数量
- 那么如果要求k个不同的差,给我们n个数(n>=k+1). 我们只需要k+1个数就可以组成k个不同的差,也就是说,有n-k-1个数,我们用不到,直接放入数组即可。剩下的依次用两边的组成不同的差。具体看下面图解:
![]()
- 极端一点的例子
![]()
代码:时间复杂度O(n) 空间复杂度O(1) |
---|
文章来源地址https://www.toymoban.com/news/detail-822615.html
class Solution {
public int[] constructArray(int n, int k) {
int[] arr = new int[n];//题目要求的返回数组
int index = 0;//数组下标
//前面n-k-1个数,我们不需要用来组成差
for(int i = 1;i<n-k;i++){
arr[index++] = i;
}
//剩下k+1个数,是我们需要组成k个差的数
//每次从两边各取一个
for(int i = n - k, j = n; i<=j; i++,j--){
arr[index++] = i;//左边取一个
//如果是奇数个,最后只会剩下一个数,那么左边和右边都指向同一个元素
//上面左边已经放了。右边再放一次就下标越界了。所以需要if(i!=j)这个判断
if(i!=j) arr[index++] = j;//右边取一个
}
return arr;//返回答案数组
}
}
到了这里,关于java数据结构与算法刷题-----LeetCode667. 优美的排列 II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!