Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commite4fc2bc

Browse files
authored
Sri Hari: Batch-5/Neetcode-ALL/Added-articles (neetcode-gh#3829)
* Batch-5/Neetcode-ALL/Added-articles* Batch-5/Neetcode-ALL/Added-articles* Batch-5/Neetcode-ALL/Added-articles* Batch-5/Neetcode-ALL/Added-articles
1 parent1063ce2 commite4fc2bc

File tree

21 files changed

+8038
-0
lines changed

21 files changed

+8038
-0
lines changed
Lines changed: 338 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,338 @@
1+
##1. Greedy
2+
3+
::tabs-start
4+
5+
```python
6+
classSolution:
7+
defrearrangeArray(self,nums: List[int]) -> List[int]:
8+
nums.sort()
9+
res= []
10+
l, r=0,len(nums)-1
11+
whilelen(res)!=len(nums):
12+
res.append(nums[l])
13+
l+=1
14+
if l<= r:
15+
res.append(nums[r])
16+
r-=1
17+
return res
18+
```
19+
20+
```java
21+
publicclassSolution {
22+
publicint[]rearrangeArray(int[]nums) {
23+
Arrays.sort(nums);
24+
int[] res=newint[nums.length];
25+
int l=0, r= nums.length-1;
26+
int idx=0;
27+
28+
while (idx!= nums.length) {
29+
res[idx++]= nums[l++];
30+
if (l<= r) {
31+
res[idx++]= nums[r--];
32+
}
33+
}
34+
35+
return res;
36+
}
37+
}
38+
```
39+
40+
```cpp
41+
classSolution {
42+
public:
43+
vector<int> rearrangeArray(vector<int>& nums) {
44+
sort(nums.begin(), nums.end());
45+
vector<int> res;
46+
int l = 0, r = nums.size() - 1;
47+
48+
while (res.size() != nums.size()) {
49+
res.push_back(nums[l++]);
50+
if (l <= r) {
51+
res.push_back(nums[r--]);
52+
}
53+
}
54+
55+
return res;
56+
}
57+
};
58+
```
59+
60+
```javascript
61+
classSolution {
62+
/**
63+
*@param{number[]}nums
64+
*@return{number[]}
65+
*/
66+
rearrangeArray(nums) {
67+
nums.sort((a,b)=> a- b);
68+
constres= [];
69+
let l=0, r=nums.length-1;
70+
71+
while (res.length!==nums.length) {
72+
res.push(nums[l++]);
73+
if (l<= r) {
74+
res.push(nums[r--]);
75+
}
76+
}
77+
78+
return res;
79+
}
80+
}
81+
```
82+
83+
::tabs-end
84+
85+
###Time & Space Complexity
86+
87+
* Time complexity: $O(n\log n)$
88+
* Space complexity: $O(n)$
89+
90+
---
91+
92+
##2. Greedy (Space Optimized)
93+
94+
::tabs-start
95+
96+
```python
97+
classSolution:
98+
defrearrangeArray(self,nums: List[int]) -> List[int]:
99+
nums.sort()
100+
for iinrange(1,len(nums),2):
101+
nums[i], nums[i-1]= nums[i-1], nums[i]
102+
return nums
103+
```
104+
105+
```java
106+
publicclassSolution {
107+
publicint[]rearrangeArray(int[]nums) {
108+
Arrays.sort(nums);
109+
for (int i=1; i< nums.length; i+=2) {
110+
int temp= nums[i];
111+
nums[i]= nums[i-1];
112+
nums[i-1]= temp;
113+
}
114+
return nums;
115+
}
116+
}
117+
```
118+
119+
```cpp
120+
classSolution {
121+
public:
122+
vector<int> rearrangeArray(vector<int>& nums) {
123+
sort(nums.begin(), nums.end());
124+
for (int i = 1; i < nums.size(); i += 2) {
125+
swap(nums[i], nums[i - 1]);
126+
}
127+
return nums;
128+
}
129+
};
130+
```
131+
132+
```javascript
133+
class Solution {
134+
/**
135+
* @param {number[]} nums
136+
* @return {number[]}
137+
*/
138+
rearrangeArray(nums) {
139+
nums.sort((a, b) => a - b);
140+
for (let i = 1; i < nums.length; i += 2) {
141+
[nums[i], nums[i - 1]] = [nums[i - 1], nums[i]];
142+
}
143+
return nums;
144+
}
145+
}
146+
```
147+
148+
::tabs-end
149+
150+
###Time & Space Complexity
151+
152+
* Time complexity: $O(n \log n)$
153+
* Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.
154+
155+
---
156+
157+
##3. Greedy (Optimal) - I
158+
159+
::tabs-start
160+
161+
```python
162+
classSolution:
163+
defrearrangeArray(self,nums: List[int]) -> List[int]:
164+
n=len(nums)
165+
166+
for iinrange(1, n-1):
167+
if2* nums[i]== (nums[i-1]+ nums[i+1]):
168+
nums[i], nums[i+1]= nums[i+1], nums[i]
169+
170+
for iinrange(n-2,0,-1):
171+
if2* nums[i]== (nums[i-1]+ nums[i+1]):
172+
nums[i], nums[i-1]= nums[i-1], nums[i]
173+
174+
return nums
175+
```
176+
177+
```java
178+
publicclassSolution {
179+
publicint[]rearrangeArray(int[]nums) {
180+
int n= nums.length;
181+
182+
for (int i=1; i< n-1; i++) {
183+
if (2* nums[i]== (nums[i-1]+ nums[i+1])) {
184+
int temp= nums[i];
185+
nums[i]= nums[i+1];
186+
nums[i+1]= temp;
187+
}
188+
}
189+
190+
for (int i= n-2; i>0; i--) {
191+
if (2* nums[i]== (nums[i-1]+ nums[i+1])) {
192+
int temp= nums[i];
193+
nums[i]= nums[i-1];
194+
nums[i-1]= temp;
195+
}
196+
}
197+
198+
return nums;
199+
}
200+
}
201+
```
202+
203+
```cpp
204+
classSolution {
205+
public:
206+
vector<int> rearrangeArray(vector<int>& nums) {
207+
int n = nums.size();
208+
209+
for (int i = 1; i < n - 1; i++) {
210+
if (2 * nums[i] == (nums[i - 1] + nums[i + 1])) {
211+
swap(nums[i], nums[i + 1]);
212+
}
213+
}
214+
215+
for (int i = n -2; i >0; i--) {
216+
if (2 * nums[i] == (nums[i - 1] + nums[i + 1])) {
217+
swap(nums[i], nums[i - 1]);
218+
}
219+
}
220+
221+
return nums;
222+
}
223+
};
224+
```
225+
226+
```javascript
227+
classSolution {
228+
/**
229+
*@param{number[]}nums
230+
*@return{number[]}
231+
*/
232+
rearrangeArray(nums) {
233+
constn=nums.length;
234+
235+
for (let i=1; i< n-1; i++) {
236+
if (2* nums[i]=== nums[i-1]+ nums[i+1]) {
237+
[nums[i], nums[i+1]]= [nums[i+1], nums[i]];
238+
}
239+
}
240+
241+
for (let i= n-2; i>0; i--) {
242+
if (2* nums[i]=== nums[i-1]+ nums[i+1]) {
243+
[nums[i], nums[i-1]]= [nums[i-1], nums[i]];
244+
}
245+
}
246+
247+
return nums;
248+
}
249+
}
250+
```
251+
252+
::tabs-end
253+
254+
###Time & Space Complexity
255+
256+
* Time complexity: $O(n)$
257+
* Space complexity: $O(1)$ extra space.
258+
259+
---
260+
261+
##4. Greedy Optimal - II
262+
263+
::tabs-start
264+
265+
```python
266+
classSolution:
267+
defrearrangeArray(self,nums: List[int]) -> List[int]:
268+
increase= nums[0]< nums[1]
269+
for iinrange(1,len(nums)-1):
270+
if ((increaseand nums[i]< nums[i+1])or
271+
(not increaseand nums[i]> nums[i+1])
272+
):
273+
nums[i], nums[i+1]= nums[i+1], nums[i]
274+
increase=not increase
275+
return nums
276+
```
277+
278+
```java
279+
publicclassSolution {
280+
publicint[]rearrangeArray(int[]nums) {
281+
boolean increase= nums[0]< nums[1];
282+
for (int i=1; i< nums.length-1; i++) {
283+
if ((increase&& nums[i]< nums[i+1])||
284+
(!increase&& nums[i]> nums[i+1])) {
285+
int temp= nums[i];
286+
nums[i]= nums[i+1];
287+
nums[i+1]= temp;
288+
}
289+
increase=!increase;
290+
}
291+
return nums;
292+
}
293+
}
294+
```
295+
296+
```cpp
297+
classSolution {
298+
public:
299+
vector<int> rearrangeArray(vector<int>& nums) {
300+
bool increase = nums[0] < nums[1];
301+
for (int i = 1; i < nums.size() - 1; i++) {
302+
if ((increase && nums[i] < nums[i + 1]) ||
303+
(!increase && nums[i] > nums[i + 1])) {
304+
swap(nums[i], nums[i + 1]);
305+
}
306+
increase = !increase;
307+
}
308+
return nums;
309+
}
310+
};
311+
```
312+
313+
```javascript
314+
class Solution {
315+
/**
316+
* @param {number[]} nums
317+
* @return {number[]}
318+
*/
319+
rearrangeArray(nums) {
320+
let increase = nums[0] < nums[1];
321+
for (let i = 1; i < nums.length - 1; i++) {
322+
if ((increase && nums[i] < nums[i + 1]) ||
323+
(!increase && nums[i] > nums[i + 1])) {
324+
[nums[i], nums[i + 1]] = [nums[i + 1], nums[i]];
325+
}
326+
increase = !increase;
327+
}
328+
return nums;
329+
}
330+
}
331+
```
332+
333+
::tabs-end
334+
335+
###Time & Space Complexity
336+
337+
* Time complexity: $O(n)$
338+
* Space complexity: $O(1)$ extra space.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp