Skip to content

Commit f5ca350

Browse files
kunal-kushwahakunal-kushwaha
committed
cyclic sort
1 parent dcf153f commit f5ca350

File tree

9 files changed

+350
-0
lines changed

9 files changed

+350
-0
lines changed

‎lectures/11-sorting/Cyclic Sort.pdf

1.75 MB
Binary file not shown.

‎lectures/11-sorting/code/.idea/uiDesigner.xml

Lines changed: 124 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎lectures/11-sorting/code/src/com/kunal/CyclicSort.java

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package com.kunal;
2+
3+
import java.util.Arrays;
4+
5+
public class CyclicSort {
6+
public static void main(String[] args) {
7+
int[] arr = {5, 4, 3, 2, 1};
8+
sort(arr);
9+
System.out.println(Arrays.toString(arr));
10+
}
11+
12+
static void sort(int[] arr) {
13+
int i = 0;
14+
while (i < arr.length) {
15+
int correct = arr[i] - 1;
16+
if (arr[i] != arr[correct]) {
17+
swap(arr, i , correct);
18+
} else {
19+
i++;
20+
}
21+
}
22+
}
23+
24+
static void swap(int[] arr, int first, int second) {
25+
int temp = arr[first];
26+
arr[first] = arr[second];
27+
arr[second] = temp;
28+
}
29+
30+
31+
}

‎lectures/11-sorting/code/src/com/kunal/FindAllDuplicates.java

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package com.kunal;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
// https://leetcode.com/problems/find-all-duplicates-in-an-array/
6+
public class FindAllDuplicates {
7+
public List<Integer> findDuplicates(int[] arr) {
8+
int i = 0;
9+
while (i < arr.length) {
10+
int correct = arr[i] - 1;
11+
if (arr[i] != arr[correct]) {
12+
swap(arr, i , correct);
13+
} else {
14+
i++;
15+
}
16+
}
17+
18+
List<Integer> ans = new ArrayList<>();
19+
for (int index = 0; index < arr.length; index++) {
20+
if (arr[index] != index+1) {
21+
ans.add(arr[index]);
22+
}
23+
}
24+
25+
return ans;
26+
}
27+
28+
static void swap(int[] arr, int first, int second) {
29+
int temp = arr[first];
30+
arr[first] = arr[second];
31+
arr[second] = temp;
32+
}
33+
}

‎lectures/11-sorting/code/src/com/kunal/FindAllMissing.java

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package com.kunal;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
// https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/
6+
// Asked in Google
7+
8+
class FindAllMissing {
9+
public List<Integer> findDisappearedNumbers(int[] nums) {
10+
int i = 0;
11+
while (i < nums.length) {
12+
int correct = nums[i] - 1;
13+
if (nums[i] != nums[correct]) {
14+
swap(nums, i , correct);
15+
} else {
16+
i++;
17+
}
18+
}
19+
20+
// just find missing numbers
21+
List<Integer> ans = new ArrayList<>();
22+
for (int index = 0; index < nums.length; index++) {
23+
if (nums[index] != index+1) {
24+
ans.add(index + 1);
25+
}
26+
}
27+
28+
return ans;
29+
}
30+
31+
static void swap(int[] arr, int first, int second) {
32+
int temp = arr[first];
33+
arr[first] = arr[second];
34+
arr[second] = temp;
35+
}
36+
}

‎lectures/11-sorting/code/src/com/kunal/FindDuplicate.java

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package com.kunal;
2+
// https://leetcode.com/problems/find-the-duplicate-number/
3+
public class FindDuplicate {
4+
public int findDuplicate(int[] arr) {
5+
int i = 0;
6+
while (i < arr.length) {
7+
8+
if (arr[i] != i + 1) {
9+
int correct = arr[i] - 1;
10+
if (arr[i] != arr[correct]) {
11+
swap(arr, i , correct);
12+
} else {
13+
return arr[i];
14+
}
15+
} else {
16+
i++;
17+
}
18+
}
19+
return -1;
20+
}
21+
22+
static void swap(int[] arr, int first, int second) {
23+
int temp = arr[first];
24+
arr[first] = arr[second];
25+
arr[second] = temp;
26+
}
27+
}

‎lectures/11-sorting/code/src/com/kunal/MissingNumber.java

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package com.kunal;
2+
// https://leetcode.com/problems/missing-number/
3+
// Amazon Question
4+
class MissingNumber {
5+
6+
public static void main(String[] args) {
7+
int[] arr = {4, 0, 2, 1};
8+
System.out.println(missingNumber(arr));
9+
}
10+
11+
public static int missingNumber(int[] arr) {
12+
int i = 0;
13+
while (i < arr.length) {
14+
int correct = arr[i];
15+
if (arr[i] < arr.length && arr[i] != arr[correct]) {
16+
swap(arr, i , correct);
17+
} else {
18+
i++;
19+
}
20+
}
21+
22+
// search for first missing number
23+
for (int index = 0; index < arr.length; index++) {
24+
if (arr[index] != index) {
25+
return index;
26+
}
27+
}
28+
29+
// case 2
30+
return arr.length;
31+
}
32+
33+
static void swap(int[] arr, int first, int second) {
34+
int temp = arr[first];
35+
arr[first] = arr[second];
36+
arr[second] = temp;
37+
}
38+
}

‎lectures/11-sorting/code/src/com/kunal/MissingPositive.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package com.kunal;
2+
// https://leetcode.com/problems/first-missing-positive/
3+
public class MissingPositive {
4+
5+
public static int firstMissingPositive(int[] arr) {
6+
int i = 0;
7+
while (i < arr.length) {
8+
int correct = arr[i] - 1;
9+
if (arr[i] > 0 && arr[i] <= arr.length && arr[i] != arr[correct]) {
10+
swap(arr, i , correct);
11+
} else {
12+
i++;
13+
}
14+
}
15+
16+
// search for first missing number
17+
for (int index = 0; index < arr.length; index++) {
18+
if (arr[index] != index + 1) {
19+
return index + 1;
20+
}
21+
}
22+
23+
// case 2
24+
return arr.length + 1;
25+
}
26+
27+
static void swap(int[] arr, int first, int second) {
28+
int temp = arr[first];
29+
arr[first] = arr[second];
30+
arr[second] = temp;
31+
}
32+
}

‎lectures/11-sorting/code/src/com/kunal/SetMismatch.java

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package com.kunal;
2+
// https://leetcode.com/problems/set-mismatch/
3+
public class SetMismatch {
4+
public int[] findErrorNums(int[] arr) {
5+
int i = 0;
6+
while (i < arr.length) {
7+
int correct = arr[i] - 1;
8+
if (arr[i] != arr[correct]) {
9+
swap(arr, i , correct);
10+
} else {
11+
i++;
12+
}
13+
}
14+
15+
// search for first missing number
16+
for (int index = 0; index < arr.length; index++) {
17+
if (arr[index] != index + 1) {
18+
return new int[] {arr[index], index+1};
19+
}
20+
}
21+
return new int[] {-1, -1};
22+
}
23+
24+
static void swap(int[] arr, int first, int second) {
25+
int temp = arr[first];
26+
arr[first] = arr[second];
27+
arr[second] = temp;
28+
}
29+
}

0 commit comments

Comments
 (0)