如何构造一个满足条件的漂亮数组？
- 内容介绍
- 文章标签
- 相关推荐
本文共计796个文字，预计阅读时间需要4分钟。
LeetCode 932. 美丽数组（中等）题目大意：给定一个固定的N，如果数组A是整数1, 2, ..., N组成的排列，判断是否存在每个i+j（i+j小于N）的元素A[i]和A[j]都不相同的数组A。标签：排序 + https://leetcode.cn/problems/beautiful-array
leetcode 932. Beautiful Array 漂亮数组(中等) 一、题目大意标签: 分治
leetcode.cn/problems/beautiful-array
对于某些固定的N，如果数组A是整数1, 2, ..., N组成的排列，使得：
对于每个i < j，都不存在k 满足i < k < j使得A[k] * 2 = A[i] + A[j]。
那么数组 A是漂亮数组。
给定N，返回任意漂亮数组A（保证存在一个）。
示例 1：
输入：4
输出：[2,1,4,3]
示例 2：
输入：5
输出：[3,1,2,5,4]
提示：
- 1 <= N <= 1000
题解参考：www.cnblogs.com/grandyang/p/12287146.html
分治法，按奇偶来分的话，因为奇数加偶数等于奇数，就不会是任何一个数字的2倍了。这就是奇偶分堆的好处，这时任意两个数字肯定不能分别从奇偶堆里取了，那可能你会问，奇数堆会不会有三个奇数打破这个规则呢？只要这个奇数堆是从一个漂亮数组按固定的规则变化而来的，就能保证一定也是漂亮数组，因为对于任意一个漂亮数组，若对每个数字都加上一个相同的数字，或者都乘上一个相同的数字，则一定还是漂亮数组，因为数字的之间的内在关系并没有改变。明白了上面这些，基本就可以解题了，假设此时已经有了一个长度为n的漂亮数组，如何将其扩大呢？可以将其中每个数字都乘以2并加1，就都会变成奇数，并且这个奇数数组还是漂亮的，然后再将每个数字都乘以2，那么都会变成偶数，并且这个偶数数组还是漂亮的，两个数组拼接起来，就会得到一个长度为 2n 的漂亮数组。就是这种思路，可以从1开始，1本身就是一个漂亮数组，然后将其扩大，注意这里要卡一个N，不能让扩大的数组长度超过N，只要在变为奇数和偶数时加个判定就行了，将不大于N的数组加入到新的数组中
public class Solution {
public int[] beautifulArray(int n) {
List<Integer> ans = new ArrayList<>();
ans.add(1);
while (ans.size() < n) {
List<Integer> t = new ArrayList<>();
for (int num : ans) {
if (num * 2 - 1 <= n) {
t.add(num * 2 - 1);
}
}
for (int num : ans) {
if (num * 2 <= n) {
t.add(num * 2);
}
}
ans = t;
}
return ans.stream() .mapToInt(Integer::intValue) .toArray();
}
}
四、总结小记
- 2022/7/9 洗衣服涤不干会有味
本文共计796个文字，预计阅读时间需要4分钟。
LeetCode 932. 美丽数组（中等）题目大意：给定一个固定的N，如果数组A是整数1, 2, ..., N组成的排列，判断是否存在每个i+j（i+j小于N）的元素A[i]和A[j]都不相同的数组A。标签：排序 + https://leetcode.cn/problems/beautiful-array
leetcode 932. Beautiful Array 漂亮数组(中等) 一、题目大意标签: 分治
leetcode.cn/problems/beautiful-array
对于某些固定的N，如果数组A是整数1, 2, ..., N组成的排列，使得：
对于每个i < j，都不存在k 满足i < k < j使得A[k] * 2 = A[i] + A[j]。
那么数组 A是漂亮数组。
给定N，返回任意漂亮数组A（保证存在一个）。
示例 1：
输入：4
输出：[2,1,4,3]
示例 2：
输入：5
输出：[3,1,2,5,4]
提示：
- 1 <= N <= 1000
题解参考：www.cnblogs.com/grandyang/p/12287146.html
分治法，按奇偶来分的话，因为奇数加偶数等于奇数，就不会是任何一个数字的2倍了。这就是奇偶分堆的好处，这时任意两个数字肯定不能分别从奇偶堆里取了，那可能你会问，奇数堆会不会有三个奇数打破这个规则呢？只要这个奇数堆是从一个漂亮数组按固定的规则变化而来的，就能保证一定也是漂亮数组，因为对于任意一个漂亮数组，若对每个数字都加上一个相同的数字，或者都乘上一个相同的数字，则一定还是漂亮数组，因为数字的之间的内在关系并没有改变。明白了上面这些，基本就可以解题了，假设此时已经有了一个长度为n的漂亮数组，如何将其扩大呢？可以将其中每个数字都乘以2并加1，就都会变成奇数，并且这个奇数数组还是漂亮的，然后再将每个数字都乘以2，那么都会变成偶数，并且这个偶数数组还是漂亮的，两个数组拼接起来，就会得到一个长度为 2n 的漂亮数组。就是这种思路，可以从1开始，1本身就是一个漂亮数组，然后将其扩大，注意这里要卡一个N，不能让扩大的数组长度超过N，只要在变为奇数和偶数时加个判定就行了，将不大于N的数组加入到新的数组中
public class Solution {
public int[] beautifulArray(int n) {
List<Integer> ans = new ArrayList<>();
ans.add(1);
while (ans.size() < n) {
List<Integer> t = new ArrayList<>();
for (int num : ans) {
if (num * 2 - 1 <= n) {
t.add(num * 2 - 1);
}
}
for (int num : ans) {
if (num * 2 <= n) {
t.add(num * 2);
}
}
ans = t;
}
return ans.stream() .mapToInt(Integer::intValue) .toArray();
}
}
四、总结小记
- 2022/7/9 洗衣服涤不干会有味