|
精华帖 (1) :: 良好帖 (0) :: 隐藏帖 (20)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-12-14
听到这书名,立刻没胃口
|
| 返回顶楼 | |
|
发表时间：2011-12-14
happysoul 写道 先给个比较蛋疼的解法
private static int[][] arr = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
private static boolean check1(int n){
int c = 0;
while(c<arr.length){
for(int i:arr[c]){
if(i==n)return true;
}
c++;
}
return false;
}
其实2维数组采用对角线切分可以简化循环次数 对此题1,4,10,15 二分可以减少很多次数值比较 例如寻找5 第一行到8的时候跳出循环比较 第二行从4开始， 小于5向右寻找，遇9跳出 第三行从10开始，大于5向左寻找，遇4跳出 第四行从15开始，大于5向左寻找，无果跳出结束 优化 如果在第一行遇到8跳出的时候数组为[0][2] 第二行应该使用[1][1]起向左寻找 第三行使用[2][1]开始向左寻找，发现[2][1]大于5，减位查找 第四行使用[3][0]开始向左寻找，最终无果跳出 减位查询可以最大化的减少对比次数，不过这种[3][3]的比较也许这效率更加蛋疼 貌似如果二维数组的行、列不相等时，这种方法会出错 |
| 返回顶楼 | |
|
发表时间：2011-12-14
这广告做的……
|
| 返回顶楼 | |
|
发表时间：2011-12-14
public static boolean isIn(int[][] arr, int num) {
int fLen = arr.length, sLen = arr[0].length; if(num > arr[fLen-1][sLen - 1] || num < arr[0][0]) return false; for(int i = 0; i < fLen; i ++) { if(arr[i][0] < num && arr[i][sLen - 1] > num) if(num > arr[i][sLen/2]) { for(int j = sLen/2; j < sLen; j ++) { if(num == arr[i][j]) return true; } } else { for(int j = 0; j < sLen/2; j ++) { if(num == arr[i][j]) return true; } } else if(num < arr[i][0]) return false; else continue; } return false; } |
| 返回顶楼 | |
|
发表时间：2011-12-14
对角线分割+两端条件判断应该是最快的了
public static boolean isIn(int[][] arr, int num) { int fLen = arr.length, sLen = arr[0].length; if(num > arr[fLen-1][sLen - 1] || num < arr[0][0]) return false; for(int i = 0; i < fLen; i ++) { if(arr[i][0] <= num && arr[i][sLen - 1] >= num) if(num > arr[i][sLen/2]) { for(int j = sLen/2; j < sLen; j ++) { if(num == arr[i][j]) return true; } } else { for(int j = 0; j < sLen/2; j ++) { if(num == arr[i][j]) return true; } } else if(num < arr[i][0]) return false; else continue; } return false; } |
| 返回顶楼 | |
|
发表时间：2011-12-14
青蛙跳的那个第一个是2的n次方种，后一个是n的n次方种。不晓得是不是哈，如果是的话，我觉得出题的人脑残不晓得大家有木意见。
|
| 返回顶楼 | |
|
发表时间：2011-12-14
最后修改：2011-12-14
import java.util.Random;
/**
* 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
* 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
* 例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7，则返回true；
* 如果查找数字5，由于数组不含有该数字，则返回false。
* <br/>
* 1 2 8 9
* 2 4 9 12
* 4 7 10 13
* 6 8 11 15
*
* @author csumissu
*/
public class algorithm {
public static void main(String[] args) {
int[][] array = genRandomArray(1500, 1000);
long beginTime = System.currentTimeMillis();
System.out.println(exists(array, 19701));
long endTime = System.currentTimeMillis();
System.out.println("耗时: " + (endTime - beginTime) + "ms");
}
/**
* 判断二维数组中是否存在指定数字.
* 算法描述: (应该将指定数字与左上角的最小值与右下角的最大值进行判断)
* 查找51
* <br/>
* 原始数组:
* 4 13 17 21 28 35 45 54 59 62
* 13 21 25 27 33 43 54 61 66 69
* 22 27 37 46 54 62 68 76 78 86
* 23 31 43 54 60 71 75 82 84 95
* 33 36 52 57 69 74 80 84 92 99
* 39 42 54 67 79 88 89 99 105 115
* 45 49 64 76 81 93 101 102 110 119
* 50 53 70 85 95 103 104 111 114 128
* 57 63 72 93 100 107 111 116 121 135
* 61 70 81 99 107 109 116 125 134 137
* <br/>
* 第一次查找:
* 判断左上角4和右下角137
* 4 13 17 21 28 35 45
* 13 21 25 27 33 43 54
* 22 27 37 46 54 62 68
* 23 31 43 54 60 71 75
* 33 36 52 57 69 74 80
* 39 42 54 67 79 88 89
* 45 49 64 76 81 93 101
* 50 53 70 85 95 103 104
* <br/>
* 第二次查找:
* 21 25 27 33 43
* 27 37 46 54 62
* 31 43 54 60 71
* 36 52 57 69 74
* 42 54 67 79 88
* 49 64 76 81 93
* <br/>
* 第三次查找:
* 37 46
* 43 54
*
* @param array 符合要求的二维数组.
* @param keyNum 要查找的数字.
* @return 如果找到返回true, 否则false
*/
private static boolean exists(int[][] array, int keyNum) {
int maxColumnNum = array[0].length - 1;
int minColumnNum = 0;
int maxRowNum = array.length - 1;
int minRowNum = 0;
do {
if (array[minRowNum][minColumnNum] == keyNum
|| array[maxRowNum][maxColumnNum] == keyNum) {
return true;
} else if (array[minRowNum][minColumnNum] > keyNum ||
keyNum > array[maxRowNum][maxColumnNum]) {
return false;
}
int tempMaxColumnNum = 0;
int tempMaxRowNum = 0;
for (int i = minColumnNum; i <= maxColumnNum; i++) {
if (array[minRowNum][i] < keyNum) {
tempMaxColumnNum = i;
} else if (array[minRowNum][i] == keyNum) {
return true;
} else {
break;
}
}
for (int i = minRowNum; i <= maxRowNum; i++) {
if (array[i][minColumnNum] < keyNum) {
tempMaxRowNum = i;
} else if (array[i][minColumnNum] == keyNum) {
return true;
} else {
break;
}
}
maxColumnNum = tempMaxColumnNum;
maxRowNum = tempMaxRowNum;
minColumnNum++;
minRowNum++;
System.out.println(maxRowNum + " - " + maxColumnNum);
System.out.println(minRowNum + " - " + minColumnNum);
} while (minRowNum <= maxRowNum && minColumnNum <= maxColumnNum);
return false;
}
/**
* 生成符合要求的二维数组.
* 算法描述:二维数组中的某个元素,要大于它左边与上边中最大的那个元素.
*
* @param rowNum 数组的行数
* @param columnNum 数组的列数
* @return 二维数组
*/
private static int[][] genRandomArray(int rowNum, int columnNum) {
Random random = new Random();
int[][] array = new int[rowNum][columnNum];
for (int i = 0; i < rowNum; i++) {
for (int j = 0; j < columnNum; j++) {
int maxElement;
if (i == 0) {
if (j == 0) {
maxElement = 0;
} else {
maxElement = array[i][j - 1];
}
} else {
if (j == 0) {
maxElement = array[i - 1][j];
} else {
maxElement = array[i - 1][j] > array[i][j - 1] ? array[i - 1][j] : array[i][j - 1];
}
}
array[i][j] = maxElement + random.nextInt(10) + 1;
System.out.print(array[i][j] + "\t" + (j == columnNum - 1 ? "\n" : ""));
}
}
return array;
}
}
|
| 返回顶楼 | |
|
发表时间：2011-12-14
最后修改：2011-12-14
开始,少判断右下角那个值了....
后面,发现效率低... |
| 返回顶楼 | |
|
发表时间：2011-12-14
这类书我没兴趣
|
| 返回顶楼 | |
|
发表时间：2011-12-14
最后修改：2011-12-14
jkxydp 写道 青蛙跳的那个第一个是2的n次方种，后一个是n的n次方种。不晓得是不是哈，如果是的话，我觉得出题的人脑残不晓得大家有木意见。
如果不是,,,? |
| 返回顶楼 | |
