1,设二维数组p的每行每列都按照下标递增的顺序递增。
用数学语言描述如下:p满足
(1),对任意的x1,x2,y,如果x1<x2,则p(x1,y)<p(x2,y);
(2),对任意的x,y1,y2, 如果y1<y2,则p(x,y1)<p(x,y2);
2,问题:
给定满足1的数组p和一个整数k,求是否存在x0,y0使得p(x0,y0)=k?
3,算法分析:
(1),穷举法,遍历二维数组,复杂度O(n*n),这个方法的代码我就不写了。
(2),二分搜索,复杂度为O(n*lgn),遍历每一行,每一列采用二分搜索。
//n*O(lgn)
public static Point search(int[][] p, int k) {
for (int i = 0; i < p.length; i++) {
int j = bSearch(p[i], 0, p[i].length, k);
if (j > 0) {
return new Point(i, j);
}
}
return null;
}
/**
* 用二分算法搜索递增数组X下标从s到e区间的值为t的元素的下标
*/
public static int bSearch(int[] X, int s, int e, int t) {
while (s <= e) {
int m = (s + e) / 2;
if (X[m] == t) {
return m;
} else if (X[m] > t) {
e = m - 1;
} else {
s = m + 1;
}
}
return -1;
}
static class Point {
int x;
int y;
public Point(int x, int y) {
super();
this.x = x;
this.y = y;
}
}
我猜想,应该存在O(lgn*lgn)的算法,暂时没有想到。
分享到:
相关推荐
二分查找,也被称为折半查找,是一种在有序数组中查找特定元素的搜索算法。其基本思想是将数组分成两半,然后比较中间元素与目标值,如果目标值等于中间元素,查找结束;如果目标值小于中间元素,则在左半部分数组中...
二维数组在计算机科学中,是一个多维数据结构,它由一串连续的内存位置组成,这些位置代表了按行和列排列的元素。每个元素可以通过一对索引(行索引和列索引)来访问。例如,一个二维数组可以表示为`arr[row][column...
在C语言中,一维数组是一系列相同类型的数据元素的集合,它们在内存中连续存储。数组的定义和初始化是学习C语言的基础知识。 1. **数组定义**: 一维数组可以定义为 `类型名 数组名[大小]`,例如 `int arr[10];` ...
二维数组是指元素全部是一个一维数组的数组。 二维数组的定义:数据类型[][] 数组名 = new 数据类型[二维数组的容量][二维数组中一维数组的容量]; 二维数组的使用: * 声明一个二维数组:使用符号[][]表示 * 数据...
上述代码中,`linearSearch二维数组`函数接受一个二维数组和一个目标值作为参数,返回一个对象,包含了目标值在数组中的位置(行和列)。如果未找到目标值,函数返回`null`。 另外,如果二维数组的每一行都是有序的...
从给定的代码片段中,我们可以提取出三个主要的知识点:二分查找算法、杨辉三角的生成以及一维和二维数组的操作。下面将详细解释这些知识点。 ### 二分查找算法 二分查找(Binary Search)是一种在有序数组中查找...
在这个实验中,通过“二维数组快速排序.vi”,你可以学习如何在LabVIEW中设计交互式界面,如何处理2D数组,以及如何实现快速排序算法。同时,也可以了解到LabVIEW中的数据操作和控制流程,这对于提高LabVIEW编程技能...
本文主要讨论的是如何在一种特殊结构的二维数组中高效地查找特定元素。这种二维数组的特点是每一行从左到右递增排序,每一列从上到下也递增排序。这种问题通常出现在算法和矩阵相关的编程题目中,对算法设计和分析有...
二维数组中的查找问题是一个典型的二分搜索算法在二维空间的应用。在这个问题中,给定一个 n * m 的二维数组,数组的每一行都是从左到右递增的,每一列都是从上到下递增的。这样的数据结构类似于一个有序的矩阵,...
在Python编程语言中,二维数组是一种常见的数据结构,它由多个一维数组组成,形成一个矩阵状的结构。在这个特定的问题中,我们处理的是一个特殊类型的二维数组,其特点是每行从左到右递增,每列从上到下递增。这样的...
一维数组是计算机科学中最基本的数据结构之一,它是一系列相同类型元素的有序集合,可以通过索引来访问和操作这些元素。数组在算法设计中扮演着重要角色,特别是在处理线性数据、查找和排序问题时。 1. **一维数组...
一维数组是最简单的数据结构之一,它是一个有序的元素集合,每个元素通过索引访问。在编程中,一维数组通常用于存储线性数据,例如数字序列。数组的大小(n)在这里被定义为全局变量,这意味着在整个程序中都可以...
一维数组是C语言程序设计的基础,理解和熟练掌握一维数组的使用是后续学习二维数组、字符数组等更复杂数据结构的基础。通过有效的教学设计,将理论知识与实践操作相结合,能激发学生的学习兴趣,提高其编程能力,为...
在数组中快速查找近似值是一项常见的编程任务,特别是在数据处理和算法设计中。这个话题主要涉及两个核心概念:数组和近似值。数组是一种线性数据结构,它存储了一组相同类型的元素,并通过索引进行访问。近似值则是...
在C#中,数组可以是一维、二维或多维的,这里我们主要关注一维数组。一维数组的声明和初始化如下: ```csharp int[] numbers = new int[5]; // 声明一个包含5个整数的一维数组 numbers[0] = 1; // 给第一个元素赋值...
在编程领域,数组是基础数据结构之一,而二维数组则是数组的一个扩展,它允许我们存储二维数据,就像表格一样。二维数组是由多个一维数组组成的,可以想象成一个矩阵或表格,每一行代表一个一维数组,列数则定义了每...
在Python编程中,二维有序数组查找是一个常见的问题,特别是在处理表格数据或矩阵时。本篇文章将深入探讨如何在二维有序数组中高效地查找特定元素。二维有序数组的特点是每一行和每一列都按照递增顺序排列,这为查找...
在给定的代码示例中,有两个程序展示了如何使用一维数组处理数据。第一个程序使用了10个单独的变量`a1`到`a10`来存储成绩,这种方法在处理大量数据时显得繁琐。第二个程序则使用了一维数组`a[11]`,更简洁且易于理解...
在JavaScript中,二维数组是一个数组,它包含的每个元素本身也是一个数组。 在示例代码中,定义了两个二维数组arr和array。第一个二维数组arr被初始化为包含四个元素的一维数组,每个一维数组包含两个数字。第二个...
1. **数组**:题目中提到了二维数组W,数组是一种线性数据结构,它以固定大小的同类型元素集合表示。数组的元素按特定顺序存储,可以通过下标访问。在本题中,数组W的每个元素占用4个字节,共有8行4列,所以总占用...