怎么创建网站平台赚钱,自己做网站升seo,专业建设方案,wordpress全站静态页面java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 解题思路 题目要求我们返回一个数组长度为n的数组#xff0c;必须含有1~n…java数据结构与算法刷题目录剑指Offer、LeetCode、ACM-----主目录-----持续更新(进不去说明我没写完)https://blog.csdn.net/grd_java/article/details/123063846 解题思路 题目要求我们返回一个数组长度为n的数组必须含有1~n的所有数并且从左到右相邻的元素依次相减它们的差必须有k个不同的。比如1,2,3,4,5 这5个数两两相减都只有一个差----1.如果想要两个不同的差就不能这么摆。可以这样1,2,3,5,4 这样就有2-1 1. 5-3 2这样两个不同的差。而且我们发现想要有k个不同的差必须至少有k1个数才能完成。大家可以尝试1~5这5个数都只能用一次然后组出相邻相减情况下的6个不同的差是不行的。最简单的做法就是用最后一个-最前面的然后依次缩小范围用过的不再使用再次用后面的-前面的。直到达到目标要求的数量那么如果要求k个不同的差给我们n个数nk1. 我们只需要k1个数就可以组成k个不同的差也就是说有n-k-1个数我们用不到直接放入数组即可。剩下的依次用两边的组成不同的差。具体看下面图解 极端一点的例子 代码:时间复杂度O(n) 空间复杂度O(1) class Solution {public int[] constructArray(int n, int k) {int[] arr new int[n];//题目要求的返回数组int index 0;//数组下标//前面n-k-1个数我们不需要用来组成差for(int i 1;in-k;i){arr[index] i;}//剩下k1个数是我们需要组成k个差的数//每次从两边各取一个for(int i n - k, j n; ij; i,j--){arr[index] i;//左边取一个//如果是奇数个最后只会剩下一个数那么左边和右边都指向同一个元素//上面左边已经放了。右边再放一次就下标越界了。所以需要if(i!j)这个判断if(i!j) arr[index] j;//右边取一个}return arr;//返回答案数组}
}
