| java數(shù)據(jù)結(jié)構(gòu)與算法刷題目錄（劍指Offer、LeetCode、ACM）-----主目錄-----持續(xù)更新(進(jìn)不去說明我沒寫完)：https://blog.csdn.net/grd_java/article/details/123063846 |
|---|
文章來源：http://www.zghlxwxcb.cn/news/detail-822615.html
| 解題思路 |
|---|
- 題目要求我們返回一個數(shù)組長度為n的數(shù)組，必須含有1~n的所有數(shù)，并且從左到右，相鄰的元素依次相減，它們的差，必須有k個不同的。比如1,2,3,4,5 這5個數(shù)兩兩相減，都只有一個差----1.如果想要兩個不同的差，就不能這么擺?？梢赃@樣1,2,3,5,4 這樣就有2-1 = 1. 5-3 = 2這樣兩個不同的差。
- 而且我們發(fā)現(xiàn)，想要有k個不同的差，必須至少有k+1個數(shù)才能完成。大家可以嘗試1~5這5個數(shù)都只能用一次，然后組出相鄰相減情況下的6個不同的差，是不行的。
- 最簡單的做法就是，用最后一個-最前面的，然后依次縮小范圍（用過的不再使用），再次用后面的-前面的。直到達(dá)到目標(biāo)要求的數(shù)量
- 那么如果要求k個不同的差，給我們n個數(shù)（n>=k+1）. 我們只需要k+1個數(shù)就可以組成k個不同的差，也就是說，有n-k-1個數(shù)，我們用不到，直接放入數(shù)組即可。剩下的依次用兩邊的組成不同的差。具體看下面圖解：
- 極端一點(diǎn)的例子
| 代碼:時間復(fù)雜度O(n) 空間復(fù)雜度O(1) |
|---|
文章來源地址http://www.zghlxwxcb.cn/news/detail-822615.html
class Solution {
public int[] constructArray(int n, int k) {
int[] arr = new int[n];//題目要求的返回數(shù)組
int index = 0;//數(shù)組下標(biāo)
//前面n-k-1個數(shù)，我們不需要用來組成差
for(int i = 1;i<n-k;i++){
arr[index++] = i;
}
//剩下k+1個數(shù)，是我們需要組成k個差的數(shù)
//每次從兩邊各取一個
for(int i = n - k, j = n; i<=j; i++,j--){
arr[index++] = i;//左邊取一個
//如果是奇數(shù)個，最后只會剩下一個數(shù)，那么左邊和右邊都指向同一個元素
//上面左邊已經(jīng)放了。右邊再放一次就下標(biāo)越界了。所以需要if(i!=j)這個判斷
if(i!=j) arr[index++] = j;//右邊取一個
}
return arr;//返回答案數(shù)組
}
}
到了這里，關(guān)于java數(shù)據(jù)結(jié)構(gòu)與算法刷題-----LeetCode667. 優(yōu)美的排列 II的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
