二维数组中的查找
在一个二维数组中，每一行按照从左到右递增顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
当我们要解决一个复杂的问题时，一个很有效的方法就是从一个具体的问题入手，通过分析简单的例子，试图寻找普遍的规律。
具体的🌰：例如下面的数组就是每行每列递增排序。如果在这个数组中查找到数字7则返回true；如果查找数字5，则返回false。
解决方法：从数组的一个角上选取数字来和要查找的数字做比较。情况会变的简单
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public boolean isNumberExist(int rows, int columns, int number) {
int[][] arrays = generalArray();
boolean flag = false;
int row = 0;
int column = columns-1;
while (column >= 0 && row < rows) {
if (arrays[row][column] > number) {
column--;
} else if (arrays[row][column] < number) {
row++;
} else {
flag = true;
break;
}
}
return flag;
}
private int[][] generalArray() {
int[][] arrays = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
return arrays;
}
|
旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3，4，5，1，2}为{1，2，3，4，5}的一个旋转，该数组的最小值为1。
调整数组顺序使奇数位于偶数前面
输入一个整数数组实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
维护两个指针，第一个指针P1初始指向数组的第一个数字，它向后移动；第二个指针P2初始指向数组的最后一个数字，它向前移动。在两个指针相遇前，P1总是位于P2前面。如果P1指向的数字是偶数，并且P2指向的是奇数，交换这两个数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| void ajust(int[] array) {
int p1 = 0;
int p2 = array.length - 1;
while (p1 < p2) {
while (!isOdd(array[p1])) {
p1++;
}
while (isOdd(array[p2])) {
p2--;
}
if (p1 < p2) {
int temp = array[p1];
array[p1] = array[p2];
array[p2] = temp;
}
}
}
private boolean isOdd(int num) {
return (num & 1) == 1;
}
|
数组中出现次数超过一半的数字
连续子数组的最大和
把数组排成最小的数
数组中的逆序对
数字在排序数组中出现的次数
数组中只出现一次的数字
数组中重复的数字
