Convert array into Zig Zag fashion | Problem of the day | GeeksForGeeks
HTML-код
- Опубликовано: 7 июн 2024
- Given an array arr of distinct elements of size n, the task is to rearrange the elements of the array in a zig-zag fashion so that the converted array should be in the below form:
arr[0] less than arr[1] greater than arr[2] less than arr[3] greater than arr[4] less than . . . . arr[n-2] less than arr[n-1] greater than arr[n].
Note: Modify the given arr[] only, If your transformation is correct, the output will be 1 else the output will be 0.
Examples
Input: n = 7, arr[] = {4, 3, 7, 8, 6, 2, 1}
Output: 3 7 4 8 2 6 1
Explanation: 3 less than 7 greater than 4 less than 8 greater than 2 less than 6 greater than 1
Input: n = 4, arr[] = {1, 4, 3, 2}
Output: 1 4 2 3
Explanation: 1 less than 4 greater than 2 less than 3
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
Table of Contents
0:00 Problem Statement
1:08 Solution - Python
4:13 Solution - C++
Keep posting.
class Solution:
def zigZag(self, n : int, arr : List[int]) -> None:
j = 1
less_than = True
while j < n:
if less_than:
if arr[j-1] > arr[j]:
temp = arr[j-1]
arr[j-1] = arr[j]
arr[j] = temp
less_than = False
else:
if arr[j-1] < arr[j]:
temp = arr[j-1]
arr[j-1] = arr[j]
arr[j] = temp
less_than = True
j += 1
Table of Contents
0:00 Problem Statement
1:08 Solution - Python
4:13 Solution - C++
class Solution {
public:
void zigZag(int n, vector &arr) {
int i = -1, j = 1;
bool less_than = true;
while (j < n) {
if (less_than) {
less_than = false;
if (arr[i + 1] > arr[j]) {
int temp = arr[i + 1];
arr[i + 1] = arr[j];
arr[j] = temp;
}
}
else {
less_than = true;
if (arr[i + 1] < arr[j]) {
int temp = arr[i + 1];
arr[i + 1] = arr[j];
arr[j] = temp;
}
}
j++;
i++;
}
/*for (i = 0; i < n; i++)
cout