932. Beautiful Array
Explanation:
To construct a beautiful array of length n, we can use a divide and conquer approach. The idea is to first build two sub-arrays, one containing odd numbers and the other containing even numbers, and then merge these arrays to form the final beautiful array. By doing so, we can ensure that the condition for a beautiful array is satisfied.
- Divide the problem by constructing beautiful arrays for odd and even numbers separately.
- For odd numbers, we can map a beautiful array of length n to a beautiful array of length (n+1)/2 by doubling each element and subtracting 1.
- For even numbers, we can map a beautiful array of length n to a beautiful array of length n/2 by doubling each element.
This recursive process helps in building the beautiful array efficiently.
Time Complexity: O(n)
Space Complexity: O(n)
:
class Solution {
public int[] beautifulArray(int n) {
List<Integer> res = new ArrayList<>();
res.add(1);
while (res.size() < n) {
List<Integer> tmp = new ArrayList<>();
for (int num : res) {
if (2 * num - 1 <= n) {
tmp.add(2 * num - 1);
}
}
for (int num : res) {
if (2 * num <= n) {
tmp.add(2 * num);
}
}
res = tmp;
}
return res.stream().mapToInt(i -> i).toArray();
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.