网页制作工具的选择与网站整体风格没有关系,江苏 江苏省住房和城乡建设厅网站,电脑浏览器打不开网页是什么原因,wordpress图片压缩软件数组
数组最简单的是数据结构#xff0c;占据一整块连续的内存并按照顺序存储数据#xff0c;创建数组时候#xff0c;我们需要首先指定数组的容量大小#xff0c;然后根据大小分配内存。即使我们只在数组中存储一个元素#xff0c;亚需要为所有数据预先分配内存#xf…数组
数组最简单的是数据结构占据一整块连续的内存并按照顺序存储数据创建数组时候我们需要首先指定数组的容量大小然后根据大小分配内存。即使我们只在数组中存储一个元素亚需要为所有数据预先分配内存因此空间使用效率差经常会有空闲区域没有得到充分利用。由于数组中内存是连续的于是可以根据下标在O(1)时间内读/写任何元素因此时间效率很高。为解决数组空间效率问题人们设计实现了多种动态数组Java中的vector。为了避免浪我们先为数组开辟一个较小的空间然后向数组添加元素的过程中当元素个数超过数组容量的时候我们会重新分配一个更大的空间接着吧之前的数据复制到新的驻足中在将之前的内存释放这样就能减少内存的浪费。但是每一层扩充数组容量都有大量的额外操作这多时间性能有负面的影响因此使用动态数组时候要尽量减少改变数组容量大小的次数。
算法题二维数组中查找
题目在一个二维数组中每一行从左到右递增顺序存储每一列都按照从上到下递增顺序排序。完成一个函数输入这样一个二维数组和一个整数输出数组中是否包含改整数以及改整数的位置。分析过程如下 例如下面二维数组每行列都递增。如果这个数组中查找数字6则返回true位置2,1。如果查找数字5返回false
1 2 3 4 5 2 4 6 8 10 3 6 9 12 15 4 8 12 16 20
错误解法分析过程如下
按照题目要求每列行都递增如上通过观察以上矩阵的特性很多同学会采用二分法步骤如下 将二维数组看成是一个现象的结构总共有20个元素left0right20 mid (leftright)/210取中间位置元素值value与目标元素key比较value key 则得出结果value key则left mid 1value key 则right mid - 1具体实现如下
/*** 错误案例* author liaojiamin* Date:Created in 13:59 2020/10/30*/
public class FindOne {public static Integer[][] getTwoDimenArray(int rows, int cloumns){Integer[][] twoDimen new Integer[rows][cloumns];for (int i 0; i rows; i) {for (int j 0; j cloumns; j) {Integer key (i1) * (j1);twoDimen[i][j] key;System.out.print(key );}System.out.println();}return twoDimen;}public static void findOneInTwoDimenArray1(int rows, int cloumns, Integer key){if(rows 0 || cloumns 0){return;}Integer[][] twoDimen getTwoDimenArray(rows, cloumns);if(twoDimen null){return;}boolean isInArray false;int keyCloumns -1;int keyRows -1;int left 0;int right rows * cloumns -1;int col cloumns;while (left right){int mid (left right) / 2;Integer value twoDimen[mid/ col][mid%col];//中间位置if(value key){keyRows mid/col;keyCloumns mid%col;isInArray true;break;}else if(value key){left mid 1;}else {right mid - 1;}}System.out.println(isInArray: isInArray position: rows: keyRows cloums: keyCloumns);}public static void main(String[] args) {findOneInTwoDimenArray1(4, 5, 8);}
}以下测试案例
//测试一正确
inPut:4,5,8
outPut:
1 2 3 4 5
2 4 6 8 10
3 6 9 12 15
4 8 12 16 20
isInArray: true position: rows:1 cloums:3
//测试二错误
input:5,4,8
1 2 3 4
2 4 6 8
3 6 9 12
4 8 12 16
5 10 15 20
isInArray: false position: rows:-1 cloums:-1如上测试用例可知以上解法是错误的原因在于虽然此二维数组每一列每一行都递增当并不代表中间元素mid之前的元素一定小于mid导致程序出错。
正确解法分析过程如下 还是将二维数组看成矩阵从中选一个元素 m与目标值key比较分三种情况分析查找 情况一 当 m key结束查找情况二 当 m key根据数组排序规则要查找的数字应该在当前选区的位置的右边或者下面 情况三 当m key同样的要查的数字应该在左边或者上面 如上分析由于需要朝招的数字相对当前选取的m的位置有可能两个区域而且有重叠这样看起来就复杂了。 我们将问题具体化。下面以上图中矩阵中查找数字7 为案例一步步分析查找过程。 之前之所以困难是我们在二维数组的中间选取的数字m 与目标值key比较这样导致下一次需要查找的两个相互重叠的区域。如果我们从数组的一个角上选取情况如下 首先选右上角数字9 9 7并且9 还在第四列的第一个数字所有7 不可能在第四列 将剩下三列看成一个新的二维数组同样选右上角 8 7 同样可以排除第三列数 将剩下两列看成一个新二维数组同样选右上角2 7那么要查找的7 可能在2的右边也可能在2 的下面因为之前的操作已经将右边的所有数据都排除了所有必定在2 的下面并且将2 这一行踢出只剩下3*2 的二维数组如下 剩下上图中同样用这个方法去右上角4 7 所以不再这一行可能在4下面剩下2*2 的二维数组 接着在取右上角 7 7 得出最终答案。
总结
以上查找过程有如下规律首先选取数组中右上角元素 如果改数字等于要查找数字结束查找如果改数字小于要查找数字踢出这个数字所在行如果这个数字大于要查找的数字踢出这个数字所在的列依次每一步都在查找范围内踢出一列或者一行逐步缩小范围。直到查询到或者为空。如下代码实现。时间复杂度 O(max(rows, cloumns))空间复杂度 O(1)
/*** * author liaojiamin* Date:Created in 13:59 2020/10/30*/
public class FindOne {public static Integer[][] getTwoDimenArray(int rows, int cloumns){Integer[][] twoDimen new Integer[rows][cloumns];for (int i 0; i rows; i) {for (int j 0; j cloumns; j) {Integer key (i1) * (j1);twoDimen[i][j] key;System.out.print(key );}System.out.println();}return twoDimen;}public static void findOneInTwoDimenArray2(int rows, int cloumns, Integer key){if(rows 0 || cloumns 0 || key null){return;}Integer[][] twoDimen getTwoDimenArray(rows, cloumns);if(twoDimen null){return;}boolean isInArray false;int keyCloumns cloumns -1;int keyRows 0;while (keyCloumns 0 keyRows rows){if(twoDimen[keyRows][keyCloumns] key){System.out.println(isInArray: isInArray position: rows: keyRows cloums: keyCloumns);break;}else if(twoDimen[keyRows][keyCloumns] key){keyCloumns --;}else {keyRows ;}}}public static void main(String[] args) {findOneInTwoDimenArray2(5, 4, 8);}
}测试用例 二维数组中查找包含的数字数组中最大值最小值介于最大最小之间的值二维数组中查找不包含的数字大于最大值小于最小值介于最大最小之前的不存在的值特殊输入 null
其他思路
以上是去右上角的数字统一可以选左下角的数字不能选左上角的数字例如选择1 1 7 那么7 位于1 的下面或者右边没有参考意义。不能选右下角的数字例如15 , 15 7那么7 位于15 的上面或者左边没有参考意义。
上一篇 数据结构与算法–实现Singleton模式 下一篇数据结构与算法–字符串字符串替换
