/**
* "有序数组中绝对值不同的数的个数"指的是,一个已经排好序的整数数组中绝对值不相同的数字的个数; 例如: [-5,-3,-1,0,3,6]
* 绝对值不同的数的个数为5,因为其中有5个不同的绝对值: 0, 1, 3, 5, 6 请返回给定有序数组中绝对值不同的数的个数. 要求: 文件名:
* AbsDistinct.java,方法名: static public int absDistinct(int a[])
*
* @author fangtengfei
* @date 2010-5-15
*/
public class AbsDistinct {
public static void main(String[] args) {
int data[] = { -5, -3, -1, 0, 3, 6, 7 };
System.out.println(absDistinct(data));
}
/**
* @param data
* @return
*/
static public int absDistinct(int data[]) {
int i = 0;
int j = data.length - 1;
int count = 0;
while (j - i > 0) {
// 去掉重复
if (j > 1 && data[j] == data[j - 1]) {
j--;
}
if (data[i] == data[i + 1]) {
i++;
}
// 拿最后一个数+最前面一个数,如果大后索引-1,如果小,前索引+1,如果相等后索引-1,前索引+1
if (data[j] + data[i] > 0) {
j--;
count++;
} else if (data[j] + data[i] == 0) {
j--;
i++;
count++;
} else if (data[j] + data[i] < 0) {
i++;
count++;
}
}
if (j == i) {
count++;
}
return count;
}
}
分享到:
相关推荐
8. 如何求数组中绝对值最小的数 9. 如何求数组连续最大和 字符串篇 1. 如何求一个字符串的所有排列 2. 如何求两个字符串的最长公共子串 3. 如何判断两个字符串是否为换位字符串 4. 如何判断两个字符串的包含关系 5...
* 必做题目:爬楼梯、斐波那契数、第 N 个泰波那契数、差的绝对值为 K 的数对数目、猜数字、拿硬币 * 选做题目:搜索旋转排序数组、搜索旋转排序数组 II、寻找旋转排序数组中的最小值、山峰数组的顶部 第四天 * 必...
(10)编写一个程序实现如下功能:调用名为tj的函数,求一个二维数组中正数、负数的代数和,以及零的个数。 (11)编写一个程序实现如下功能:调用一个名为gm的函数,该函数实现简单的加密。加密方法如下:先定义...
5. 有序数组构建二叉树:可以使用中序遍历的方法,将数组元素依次插入二叉搜索树。 6. 层次遍历二叉树:利用队列进行广度优先搜索(BFS)可以实现。 7. 链表反转:通过改变节点的next指针,使其指向前一个节点,...
5. **有序数组到二叉树**:可以使用二叉搜索树的概念,自底向上或自顶向下构建。 6. **逐层打印二叉树**:广度优先搜索(BFS)是一种常用方法。 7. **链表反转**:可以通过迭代或递归的方式改变链接关系来实现。 ...
15. **数列中数对的个数**:使用哈希表记录每个元素出现的次数,然后遍历计算满足条件的数对。 谷歌面试题: 1. **设计序列生成函数**:可以使用循环和条件判断生成序列。 2. **字符串处理**:通过遍历和字符比较...
将有序数组转化为二叉树** - **知识点**: 数据结构、二叉树构建 - **解析**: 从中位数开始构建二叉树,中位数作为根节点,左侧的元素构成左子树,右侧的元素构成右子树,递归地构建整个二叉树。 **6. 二叉树的...
有序数组转二叉树** - **题目描述**:编写一个程序,把一个有序整数数组放到二叉树中。 - **解决方案**:可以使用递归方法,每次选取中间元素作为根节点,然后分别构建左右子树。 **6. 逐层打印二叉树结点数据** ...
- **二进制中1的个数**: 计算二进制表示中1的个数,可以使用位操作配合加法和减法。 - **缺失的数字**: 在有序序列中找出缺失的数字,位操作可以帮助快速定位。 学习并熟练掌握这些位运算技巧,不仅能够提升编程...
- **答案解析**: 归并两个有序数组的最坏情况发生在两个数组完全交错的情况下,此时每次比较都需要进行。合并两个长度为n的数组,需要比较2n-1次,故正确答案是D. 2n-1。 #### 12. 在 n(n>=3)枚硬币中有一枚质量不...
- **向量**:向量是具有方向和大小的量,在线性代数中通常表示为有序数组。 - **矩阵**:由数按照一定方式排列成的矩形阵列,是线性代数的重要工具之一。矩阵可以用来表示线性变换,也可以用于解决线性方程组等问题...
9. **顺序表的折半查找**:折半查找是一种在有序数组中查找元素的高效方法。第9题中,查找不存在的元素,最多比较次数为log2(n)+1次,对于16个元素,最多比较6次。 10. **快速排序的递归次数**:快速排序的递归次数...
- **解析**: 归并两个有序数组的最坏情况是比较次数等于数组的总长度。因此,合并两个长度为n的数组至少需要做2n-1次比较。正确答案是**D. 2n-1**。 **18. 从哪一年开始,NOIP竞赛将不再支持Pascal语言?** - **...
- 使用邻接矩阵来表示图时,矩阵中的元素表示两个顶点之间的关联关系,矩阵元素的个数与图中的顶点数相关,而非边的数量。 8. **图的遍历**: - 图的深度优先遍历和广度优先遍历可以产生不同的遍历序列,这些序列...
设A和B是两个长为n的有序数组,现在需要将A和B合并成一个排好序的数组,任何以元素比较作为基本运算的归并算法在最坏情况下至少要做()次比较** - **解析:** 最坏情况下,每次比较只能确定一个元素的位置,因此...
3. 在一个具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 O(n)。 4. 稀疏矩阵一般的压缩存储方法有两种,即三元组压缩和按行压缩。 5. 具有 n 个顶点的有向图最多有 n*(n-1) 条边。 6. 在无向...
题目中提到“串的长度是( )”,串的长度是指串中所有字符的数量,无论这些字符是否相同,所以正确答案是D)“串中所有字符的个数”。 哈夫曼树是一种特殊的二叉树,用于数据压缩,它的特点是带权路径长度最短,...
如果在插入一个元素之后,红黑树的黑高度(树中黑色节点的个数)增加了,那么在双红修正过程中,只有颜色的改变,而没有拓扑结构的变化。 3. KMP算法是一种字符串匹配算法,当不使用改进版的next数组时,在最坏的...
- 第9题:在有序表`A[1..20]`中,按二分查找方法进行查找,查找长度为5的元素个数是4个。这是因为二分查找每次排除一半的元素,直到找到目标元素或搜索区间为空。查找长度为5,意味着进行了5次比较,即搜索了16个...