703904. Sort first half in ascending and second half in descending
Sort first half in ascending and second half in descending
Summary
Given an array, sort the first half in ascending order and the second half in descending order. This problem involves manipulating arrays and sorting algorithms.
Detailed Explanation
To solve this problem, we can divide the given array into two halves: the first half and the second half. Then, we sort the first half in ascending order using a standard sorting algorithm like quicksort or mergesort. Next, we reverse the second half to sort it in descending order. Finally, we concatenate the two sorted halves to get the final result.
Here's a step-by-step breakdown of the solution:
- Calculate the middle index of the array (rounded down if the length is odd).
- Sort the first half of the array using a standard sorting algorithm.
- Reverse the second half of the array to sort it in descending order.
- Concatenate the two sorted halves to get the final result.
Time complexity: O(n log n) for the initial sorting and reversing operations, where n is the length of the array. Space complexity: O(1), as we only use a constant amount of space to store temporary variables.
Optimized Solutions
Java
public static int[] sortFirstHalfAscendingAndSecondHalfDescending(int[] arr) {
int mid = (arr.length / 2);
int[] firstHalf = Arrays.copyOfRange(arr, 0, mid);
int[] secondHalf = Arrays.copyOfRange(arr, mid, arr.length);
Arrays.sort(firstHalf);
int i = secondHalf.length - 1;
for (int j = 0; j < secondHalf.length; j++) {
secondHalf[j] = secondHalf[i--];
}
int[] result = new int[arr.length];
System.arraycopy(firstHalf, 0, result, 0, mid);
System.arraycopy(secondHalf, 0, result, mid, arr.length - mid);
return result;
}