Skip to content

Commit 676259c

Browse files
h2plh2pl
committed
数组和矩阵。完成
有一些技巧，主要是排序，二分查找等方法。也可以空间换时间。
1 parent 4deef20 commit 676259c

10 files changed

Lines changed: 273 additions & 2 deletions

‎src/数据结构/数组与矩阵/分隔数组.java‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package 数据结构.数组与矩阵;
2+
3+
/**
4+
* Created by 周杰伦 on 2018/4/18.
5+
*/
6+
public class 分隔数组 {
7+
// 先拆分成若干个数组，每个数组排序
8+
// 如果结果拼起来与原数组的排序相同，则符合。找出可以分隔的最大份数。
9+
10+
//倒序的放在一起，顺序的拆开，遇到逆序不加，遇到顺序加加。
11+
//注意遇到顺序时，需要与之前的最大值比较。比如18234这种情况，实际上只能分为2个部分。
12+
public static void main(String[] args) {
13+
int []a = {2,0,1};
14+
int []b = {4,3,2,1,0};
15+
int []c = {1,0,2,3,4};
16+
int []d = {1,2,0,3};
17+
System.out.println(maxChunksToSorted(a));
18+
System.out.println(maxChunksToSorted(b));
19+
System.out.println(maxChunksToSorted(c));
20+
System.out.println(maxChunksToSorted(d));
21+
}
22+
// 不会，待解
23+
public static int maxChunksToSorted(int[] arr) {
24+
if (arr == null) return 0;
25+
int ret = 0;
26+
int right = arr[0];
27+
for (int i = 0; i < arr.length; i++) {
28+
right = Math.max(right, arr[i]);
29+
if (right == i) ret++;
30+
}
31+
return ret;
32+
}
33+
// public static int maxChunksToSorted(int[] arr) {
34+
// int cnt = 1;
35+
// int max = arr[0];
36+
// for (int i = 1;i < arr.length;i ++) {
37+
// if (arr[i] > arr[i - 1] && arr[i] > max ) {
38+
// cnt ++;
39+
// }
40+
// max = Math.max(max, arr[i]);
41+
// }
42+
// return cnt;
43+
// }
44+
}

‎src/数据结构/数组与矩阵/寻找所有丢失的元素.java‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package 数据结构.数组与矩阵;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.Collections;
6+
import java.util.List;
7+
8+
/**
9+
* Created by 周杰伦 on 2018/4/18.
10+
*/
11+
public class 寻找所有丢失的元素 {
12+
public static void main(String[] args) {
13+
int []a = {4,3,2,7,8,2,3,1};
14+
System.out.println(findDisappearedNumbers(a));
15+
}
16+
public static List<Integer> findDisappearedNumbers(int[] nums) {
17+
int []arr = new int[nums.length + 1];
18+
ArrayList<Integer> list = new ArrayList<>();
19+
for (int i = 0;i < nums.length;i ++) {
20+
arr[nums[i]] = 1;
21+
}
22+
for (int i = 1;i < arr.length;i ++) {
23+
if (arr[i] != 1) {
24+
list.add(i);
25+
}
26+
}
27+
return list;
28+
}
29+
}

‎src/数据结构/数组与矩阵/寻找所有重复的元素.java‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package 数据结构.数组与矩阵;
2+
3+
import java.sql.Array;
4+
import java.util.ArrayList;
5+
import java.util.List;
6+
7+
/**
8+
* Created by 周杰伦 on 2018/4/18.
9+
*/
10+
public class 寻找所有重复的元素 {
11+
public static void main(String[] args) {
12+
int []a = {4,3,2,7,8,2,3,1};
13+
System.out.println(findDuplicates(a));
14+
}
15+
public static List<Integer> findDuplicates(int[] nums) {
16+
ArrayList<Integer> list = new ArrayList<>();
17+
int []arr = new int[nums.length + 1];
18+
for (int i = 0;i < nums.length;i ++) {
19+
if (arr[nums[i]] == 0) {
20+
arr[nums[i]] = 1;
21+
}else {
22+
arr[nums[i]] = 2;
23+
}
24+
}
25+
for (int i = 1;i < arr.length;i ++) {
26+
if (arr[i] == 2) {
27+
list.add(i);
28+
}
29+
}
30+
return list;
31+
}
32+
}

‎src/数据结构/数组与矩阵/嵌套数组.java‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package 数据结构.数组与矩阵;
2+
3+
import java.util.HashSet;
4+
import java.util.Set;
5+
6+
/**
7+
* Created by 周杰伦 on 2018/4/18.
8+
*/
9+
public class 嵌套数组 {
10+
public static void main(String[] args) {
11+
int []a = {5,4,0,3,1,6,2};
12+
System.out.println(arrayNesting(a));
13+
}
14+
// 访问矩阵的设置用意在于 每次从头开始访问能经历的所有元素都已经标记。
15+
// 后面如果有按照该路径访问的序列，长度都不会比此次序列长。
16+
public static int arrayNesting(int[] nums) {
17+
int cnt = 0;
18+
int max = 0;
19+
for (int j = 0;j < nums.length;j ++ ) {
20+
int index = j;
21+
cnt = 0;
22+
while (index < nums.length && nums[index] != -1) {
23+
cnt ++;
24+
int t = nums[index];
25+
nums[index] = -1;
26+
index = t;
27+
}
28+
max = Math.max(cnt, max);
29+
}
30+
return max;
31+
}
32+
}

‎src/数据结构/数组与矩阵/找出丢失的数和重复的数.java‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
package 数据结构.数组与矩阵;
2+
3+
import java.lang.reflect.Array;
4+
import java.util.Arrays;
5+
6+
/**
7+
* Created by 周杰伦 on 2018/4/18.
8+
*/
9+
public class 找出丢失的数和重复的数 {
10+
public static void main(String[] args) {
11+
int []a = {1,5,3,2,2,7,6,4,8,9};
12+
//[1,5,3,2,2,7,6,4,8,9]
13+
int []b = {3,2,3,4,6,5};
14+
//[3,2,3,4,6,5]
15+
//233456
16+
System.out.println(Arrays.toString(findErrorNums(b)));
17+
//1223456789
18+
//233456
19+
//1234556
20+
System.out.println(Arrays.toString(findErrorNums(a)));
21+
}
22+
//先找重复，再找丢失
23+
public static int[] findErrorNums(int[] nums) {
24+
Arrays.sort(nums);
25+
int []arr = new int[2];
26+
int r = 0;
27+
for (int i = 0;i < nums.length - 1;i ++) {
28+
if (nums[i] == nums[i + 1]) {
29+
arr[0] = nums[i];
30+
r = i;
31+
break;
32+
}
33+
}
34+
for (int i = 0;i <= r;i ++) {
35+
if (i + 1 != nums[i]) {
36+
arr[1] = i + 1;
37+
break;
38+
}
39+
}
40+
if (arr[1] == 0) {
41+
42+
for (int i = r + 1; i < nums.length; i++) {
43+
if (i != nums[i]) {
44+
arr[1] = i;
45+
break;
46+
}
47+
}
48+
}
49+
if (arr[1] == 0) {
50+
arr[1] = nums.length;
51+
}
52+
return arr;
53+
}
54+
}

‎src/数据结构/数组与矩阵/找出数组中重复的数有条件限制.java‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package 数据结构.数组与矩阵;
2+
3+
import java.util.ArrayList;
4+
5+
/**
6+
* Created by 周杰伦 on 2018/4/18.
7+
*/
8+
public class 找出数组中重复的数有条件限制 {
9+
public int findDuplicate(int[] nums) {
10+
ArrayList<Integer> list = new ArrayList<>();
11+
int []arr = new int[nums.length + 1];
12+
for (int i = 0;i < nums.length;i ++) {
13+
if (arr[nums[i]] == 0) {
14+
arr[nums[i]] = 1;
15+
}else {
16+
arr[nums[i]] ++;
17+
}
18+
}
19+
for (int i = 1;i < arr.length;i ++) {
20+
if (arr[i] > 1) {
21+
return i;
22+
}
23+
}
24+
return 0;
25+
}
26+
}

src/数据结构/数组与矩阵/对角元素相等的矩阵.java renamed to src/数据结构/数组与矩阵/矩阵/对角元素相等的矩阵.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package 数据结构.数组与矩阵;
1+
package 数据结构.数组与矩阵.矩阵;
22

33
/**
44
* Created by 周杰伦 on 2018/4/17.

‎src/数据结构/数组与矩阵/矩阵/有序矩阵查找.java‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package 数据结构.数组与矩阵.矩阵;
2+
3+
/**
4+
* Created by 周杰伦 on 2018/4/18.
5+
*/
6+
public class 有序矩阵查找 {
7+
public static void main(String[] args) {
8+
int [][]a = {
9+
{1, 4, 7, 11, 15},
10+
{2, 5, 8, 12, 19},
11+
{3, 6, 9, 16, 22},
12+
{10, 13, 14, 17, 24},
13+
{18, 21, 23, 26, 30}
14+
};
15+
System.out.println(searchMatrix(a,5));
16+
System.out.println(searchMatrix(a,20));
17+
18+
}
19+
public static boolean searchMatrix(int[][] matrix, int target) {
20+
if (matrix.length == 0)return false;
21+
for (int i = matrix[0].length - 1,j = 0;i >= 0 && j < matrix.length;) {
22+
if (target < matrix[j][i]) {
23+
i --;
24+
}else if (target > matrix[j][i]) {
25+
j ++;
26+
}else {
27+
return true;
28+
}
29+
}
30+
return false;
31+
}
32+
}

‎src/数据结构/数组与矩阵/矩阵/有序矩阵查找第n小的数可重复.java‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package 数据结构.数组与矩阵.矩阵;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* Created by 周杰伦 on 2018/4/18.
7+
*/
8+
public class 有序矩阵查找第n小的数可重复 {
9+
public int kthSmallest(int[][] matrix, int k) {
10+
int m = matrix.length;
11+
int n = matrix[0].length;
12+
int []arr = new int[m * n];
13+
int w = 0;
14+
for (int i = 0;i < m;i ++) {
15+
for (int j = 0;j < n;j ++) {
16+
arr[w ++] = matrix[i][j];
17+
}
18+
}
19+
Arrays.sort(arr);
20+
return arr[k - 1];
21+
}
22+
}

src/数据结构/数组与矩阵/调整矩阵.java renamed to src/数据结构/数组与矩阵/矩阵/调整矩阵.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package 数据结构.数组与矩阵;
1+
package 数据结构.数组与矩阵.矩阵;
22

33
/**
44
* Created by 周杰伦 on 2018/4/17.

0 commit comments

Comments
 (0)