`
fantasy
  • 浏览: 513703 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

有序数组中绝对值不同的数的个数

J# 
阅读更多
/**
 * "有序数组中绝对值不同的数的个数"指的是,一个已经排好序的整数数组中绝对值不相同的数字的个数; 例如: [-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;
 }
}

 

 

分享到:
评论

相关推荐

    《C 程序员面试算法宝典》读书笔记模板x.pptx

    8. 如何求数组中绝对值最小的数 9. 如何求数组连续最大和 字符串篇 1. 如何求一个字符串的所有排列 2. 如何求两个字符串的最长公共子串 3. 如何判断两个字符串是否为换位字符串 4. 如何判断两个字符串的包含关系 5...

    86txysRom08hSmz.pdf

    * 必做题目:爬楼梯、斐波那契数、第 N 个泰波那契数、差的绝对值为 K 的数对数目、猜数字、拿硬币 * 选做题目:搜索旋转排序数组、搜索旋转排序数组 II、寻找旋转排序数组中的最小值、山峰数组的顶部 第四天 * 必...

    上海电机学院C语言实训答案

    (10)编写一个程序实现如下功能:调用名为tj的函数,求一个二维数组中正数、负数的代数和,以及零的个数。 (11)编写一个程序实现如下功能:调用一个名为gm的函数,该函数实现简单的加密。加密方法如下:先定义...

    微软面试15题

    5. 有序数组构建二叉树:可以使用中序遍历的方法,将数组元素依次插入二叉搜索树。 6. 层次遍历二叉树:利用队列进行广度优先搜索(BFS)可以实现。 7. 链表反转:通过改变节点的next指针,使其指向前一个节点,...

    微软谷歌等各大公司面试题目

    5. **有序数组到二叉树**:可以使用二叉搜索树的概念,自底向上或自顶向下构建。 6. **逐层打印二叉树**:广度优先搜索(BFS)是一种常用方法。 7. **链表反转**:可以通过迭代或递归的方式改变链接关系来实现。 ...

    Java 微软面试题

    15. **数列中数对的个数**:使用哈希表记录每个元素出现的次数,然后遍历计算满足条件的数对。 谷歌面试题: 1. **设计序列生成函数**:可以使用循环和条件判断生成序列。 2. **字符串处理**:通过遍历和字符比较...

    微软google面试题

    将有序数组转化为二叉树** - **知识点**: 数据结构、二叉树构建 - **解析**: 从中位数开始构建二叉树,中位数作为根节点,左侧的元素构成左子树,右侧的元素构成右子树,递归地构建整个二叉树。 **6. 二叉树的...

    微软、谷歌、百度等公司经典面试100题[第101-170题].pdf

    有序数组转二叉树** - **题目描述**:编写一个程序,把一个有序整数数组放到二叉树中。 - **解决方案**:可以使用递归方法,每次选取中间元素作为根节点,然后分别构建左右子树。 **6. 逐层打印二叉树结点数据** ...

    位运算的妙用

    - **二进制中1的个数**: 计算二进制表示中1的个数,可以使用位操作配合加法和减法。 - **缺失的数字**: 在有序序列中找出缺失的数字,位操作可以帮助快速定位。 学习并熟练掌握这些位运算技巧,不仅能够提升编程...

    信息学竞赛真题_2591.pdf

    - **答案解析**: 归并两个有序数组的最坏情况发生在两个数组完全交错的情况下,此时每次比较都需要进行。合并两个长度为n的数组,需要比较2n-1次,故正确答案是D. 2n-1。 #### 12. 在 n(n&gt;=3)枚硬币中有一枚质量不...

    2008考研数学线性代数辅导讲义(李永乐)

    - **向量**:向量是具有方向和大小的量,在线性代数中通常表示为有序数组。 - **矩阵**:由数按照一定方式排列成的矩形阵列,是线性代数的重要工具之一。矩阵可以用来表示线性变换,也可以用于解决线性方程组等问题...

    计算机考研专业课真题与答案解析.doc

    9. **顺序表的折半查找**:折半查找是一种在有序数组中查找元素的高效方法。第9题中,查找不存在的元素,最多比较次数为log2(n)+1次,对于16个元素,最多比较6次。 10. **快速排序的递归次数**:快速排序的递归次数...

    第23届NOIP普及组C++语言试题

    - **解析**: 归并两个有序数组的最坏情况是比较次数等于数组的总长度。因此,合并两个长度为n的数组至少需要做2n-1次比较。正确答案是**D. 2n-1**。 **18. 从哪一年开始,NOIP竞赛将不再支持Pascal语言?** - **...

    杭州电子科技大学2011数据结构期末试卷

    - 使用邻接矩阵来表示图时,矩阵中的元素表示两个顶点之间的关联关系,矩阵元素的个数与图中的顶点数相关,而非边的数量。 8. **图的遍历**: - 图的深度优先遍历和广度优先遍历可以产生不同的遍历序列,这些序列...

    2017年第二十三届NOIP(C语言)普及组初赛试题及详细答案

    设A和B是两个长为n的有序数组,现在需要将A和B合并成一个排好序的数组,任何以元素比较作为基本运算的归并算法在最坏情况下至少要做()次比较** - **解析:** 最坏情况下,每次比较只能确定一个元素的位置,因此...

    2020-2021学年第二学期计算机科学与技术专业《数据结构(C语言)》期末考试题(试卷A).pdf

    3. 在一个具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 O(n)。 4. 稀疏矩阵一般的压缩存储方法有两种,即三元组压缩和按行压缩。 5. 具有 n 个顶点的有向图最多有 n*(n-1) 条边。 6. 在无向...

    2011级A1

    题目中提到“串的长度是( )”,串的长度是指串中所有字符的数量,无论这些字符是否相同,所以正确答案是D)“串中所有字符的个数”。 哈夫曼树是一种特殊的二叉树,用于数据压缩,它的特点是带权路径长度最短,...

    【期末】 2016期末.pdf

    如果在插入一个元素之后,红黑树的黑高度(树中黑色节点的个数)增加了,那么在双红修正过程中,只有颜色的改变,而没有拓扑结构的变化。 3. KMP算法是一种字符串匹配算法,当不使用改进版的next数组时,在最坏的...

    合工大1999年《数据结构》考研真题.pdf

    - 第9题:在有序表`A[1..20]`中,按二分查找方法进行查找,查找长度为5的元素个数是4个。这是因为二分查找每次排除一半的元素,直到找到目标元素或搜索区间为空。查找长度为5,意味着进行了5次比较,即搜索了16个...

Global site tag (gtag.js) - Google Analytics