`

已排序数组 a,求其元素的绝对值 共有多少个不同的值

阅读更多

已排序数组 a,求其元素的绝对值 共有多少个不同的值?

 

思路:

      2个 index,从最接近0的2个元素开始向2端遍历,每次先比较2个index所在的元素的绝对值,取小值,与最后1次的值比较,如果大于,则 count++,并将该值设为 最后一次的值,然后将小的那个 index 向前进的方向加1,

 

算法的复杂度:

      因为只要遍历1次,因此复杂度是 o(n),n是数组的个数,

 

内存占用:

     需要2个 index,1个 last,1个 count,因此除数组外,额外占用的内存是固定的,即 o(1)

 

代码:

package test;

public class Test {
	public static void main(String[] args) {
		int[] is = new int[] { -10, -9, -9, -5, -4, -3, -3, -2, -1, 0, 1, 2, 5, 6, 7, 8, 9, 11, 13, 14 };
		System.out.println(funOne(is, locateNumInSortedArray(0, is)));
	}

	/**
	 * 求 已排序数组中,不同的 绝对值的个数,这里假设数组中有0,
	 * 如果数组中没有 0 可以另写方法找最接近0的2个数 的 index,并稍修改下方法对 count 值的初始化,
	 * @param arr
	 * @param zeroIndex
	 * @return
	 */
	public static int funOne(int[] arr, int zeroIndex) {
		int plusIndex = zeroIndex + 1, negativeIndex = zeroIndex - 1;
		int last = arr[zeroIndex];
		int count = 1;
		while (negativeIndex >= 0 || plusIndex < arr.length) {
			if (negativeIndex >= 0 && plusIndex < arr.length) {// both side continue
				// x = small abs(...)
				int x1;
				int absNeg = Math.abs(arr[negativeIndex]);
				if (absNeg > arr[plusIndex]) {
					x1 = arr[plusIndex];
					plusIndex += 1;

				} else if (absNeg < arr[plusIndex]) {
					x1 = absNeg;
					negativeIndex -= 1;
				} else {
					x1 = arr[plusIndex];
					plusIndex += 1;
					negativeIndex -= 1;
				}
				if (x1 > last) {
					count++;
					last = x1;
				}
			} else if (negativeIndex >= 0) { // only negative site continue
				int x2 = Math.abs(arr[negativeIndex]);
				negativeIndex -= 1;
				if (x2 > last) {
					count++;
					last = x2;
				}
			} else { // only plus site continue
				int x3 = arr[plusIndex];
				plusIndex += 1;
				if (x3 > last) {
					count++;
					last = x3;
				}
			}

		}
		return count;
	}

	/**
	 * locate num in a sorted array
	 * @param num number to locate
	 * @param arr sorted array in asc order
	 * @return index of the num in array.If not find,-1 will be return.
	 */
	public static int locateNumInSortedArray(int num, int[] arr) {
		if (arr.length == 0 || arr[0] > num || arr[arr.length - 1] < num) {
			return -1;
		}

		int startIndex = 0, endIndex = arr.length - 1;
		while (startIndex <= endIndex) {
			int middleIndex = (startIndex + endIndex) >> 1;
			if (num == arr[middleIndex]) {
				return middleIndex;
			} else if (num > arr[middleIndex]) {
				startIndex = middleIndex + 1;
			} else {
				endIndex = middleIndex - 1;
			}
		}
		return -1;
	}
}
 
分享到:
评论

相关推荐

    实对称矩阵的每行元素绝对值之和,则特征值小于11

    这个关系意味着,对于任何特征向量x,矩阵A乘以其自身的结果的范数(即Axxl)等于λ乘以x的范数的平方(xxl),而这里提到的范数是矩阵的行范数,即矩阵每一行元素绝对值之和的最大值。 当我们讨论特征值小于11的...

    数据结构(JAVA)求一个含有n个整数元素的数组a0..n-1中的最大元素

    在Java编程语言中,解决这个问题的方法多种多样,但这里提到的思路是通过逐步比较数组中的元素来找到最大值。这种方法被称为线性搜索,因为它的复杂度与数组的长度成正比。 首先,我们需要理解数组的基本概念。数组...

    1.给出一个整数数组,求其中任意两个元素之差的最大值。

    首先对数组进行排序,然后计算排序后数组中最大值与最小值之间的差,这个差即为所求的最大值。 #### 代码解析 在给定的部分代码中,作者采用了冒泡排序算法对数组进行排序。具体实现步骤如下: 1. **初始化数组**:...

    java面试题-leetcode题解之第34题在排序数组中查找元素的第一个和最后一个位置.zip

    第34题,"在排序数组中查找元素的第一个和最后一个位置",是这样一类问题:它不仅测试了基本的数组操作,还涉及到二分查找的高级应用。下面我们将详细探讨这个问题以及相关的知识点。 ### 问题描述 给定一个已排序...

    HDU ACM 绝对值排序 txt格式

    例如,对于数组`[-3, 1, -2, 4]`,其绝对值排序结果应为`[1, -2, -3, 4]`。 ##### 3. C++语言基础 该代码片段使用了C++语言,并包含了标准输入输出库`&lt;iostream&gt;`和数学函数库`&lt;cmath&gt;`。其中,`using namespace ...

    Matlab数组排序详解docx文档下载

    例如,`sort(A,'ComparisonMethod','abs')`会根据元素的绝对值进行排序,而不是它们的原始值。 5. **返回索引**: `[B,I] = sort(___)` 除了返回排序后的数组`B`之外,还会返回一个索引向量`I`,`I`的大小与`A`...

    请给出一个高效的程序找出2个位置(开始和结束),使从一个A[start]到A[end]的和绝对值最大,并返回这个值(最大值)。

    //请给出一个高效的程序找出2个位置(开始和结束),使从一个A[start]到A[end]的和绝对值最大,并返回这个值(最大值)。 //例 A[5]={2,-1,4,-3,2};该数组最大和的子集合:起始位置为“0”,结束位置为“2” ,最大值为5...

    计组课设,A题输入包含5个整数(有符号数)的数组M,输出最大负数的绝对值

    3. **最大负数的查找**:编程时,我们需要遍历数组M,比较每个元素的值,找出最小的负数。由于我们要找的是最大负数的绝对值,因此实际上是在找最小的负整数。 4. **绝对值计算**:在计算机编程中,获取一个数的...

    matlab开发-最大绝对值设置最大绝对值

    在MATLAB编程环境中,`maxabs`函数是一个非常实用的工具,用于找出向量、矩阵或数组中的最大绝对值。这个函数是MATLAB语言基础的一部分,对于数据分析、数值计算以及算法开发有着广泛的应用。现在,让我们深入探讨...

    matlab数组排序.docx

    例如,`sort(A,'ComparisonMethod','abs')`会按照元素的绝对值进行排序,而非其实际值。 5. **返回索引**:`[B,I] = sort(___)`,这不仅返回排序后的数组`B`,还会返回一个索引向量`I`,`I`的大小与`A`相同,指示了...

    求一个实数的绝对值

    用C语言写求一个实数绝对值的代码 #include int main(void) { float a; printf("a=:"); scanf("%f",&a); if(a) a=-a; else a=a; printf("%f\n",a); return 0; }

    多个java小程序将byte 类型的绝对值, 数组最大最下元素,数字字符转化为数字

    public class exercessinto { byte y; double sum;... public void juedui(byte x)//&lt;一&gt;byte绝对值问题 { y=(byte)Math.abs(x); System.out.println("byte类型的数字的绝对值为:"+y); }

    数组实训.doc

    2. **冒泡排序法**:冒泡排序是一种简单的排序算法,它通过不断交换相邻的两个元素来逐步排序数组。在这个例子中,定义了一个整数数组`a`,然后使用两个嵌套循环,外层循环控制比较的趟数,内层循环进行两两比较并...

    用VB编写的求一个数的绝对值,调用function函数来实现

    `Function`是过程的一种,它可以返回一个值给调用它的语句。这与`Sub`过程不同,`Sub`过程只执行一系列操作,但不返回任何值。下面是一个简单的`Function`定义的例子: ```vb Function 绝对值(ByVal 数字 As Double...

    数组输出1

    在编程和算法设计中,"数组输出1" 这个问题是一个典型的数组处理任务,它涉及到查找数组中的最大绝对值元素以及返回其对应的下标。这个问题可以被看作是线性搜索的一种特殊情况,因为我们需要遍历整个数组来找到具有...

    定义比较器,比较数组中值大小

    假设我们有一个整数数组,我们希望按照元素的绝对值大小进行排序,可以创建如下的比较器类: ```java import java.util.Comparator; public class AbsValueComparator implements Comparator&lt;Integer&gt; { @...

    c++实现数组或容器排序

    本文将深入探讨如何在C++中实现数组和容器的排序,并涵盖几种不同的排序算法。 首先,对于基本类型的数组,C++标准库提供了一个非常方便的函数`std::sort`,它位于`&lt;algorithm&gt;`头文件中。例如,如果你有一个整数数...

    初一数学压轴题绝对值化简求值.pdf

    初一数学压轴题绝对值化简求值。 本资源内容涵盖了初一数学压轴题中的绝对值化简求值知识点,包括绝对值的代数意义、绝对值化简、有理数运算、平方和绝对值的非负性、二元一次方程组等。 一、初一数学压轴题:...

    关于数组的几道面试题1

    6. **求两个有序数组的共同元素**: 对于两个有序数组,可以采用双指针法,分别从头开始比较,找到相同的元素。 7. **求三个数组的共同元素**: 可以先找出两个数组的交集,再找这个交集与其他数组的交集。 8. *...

    汇编语言 20个练习题目 代码加实验报告

    5.15 数据段中已定义了一个有N个字数据的数组M,试编写一程序求出M中绝对值最大的数,把它放在数据段的M+2n单元中,并将该数的偏移地址存放在M+2(n+1)单元中。 5.16 在首地址为DATA的字数组中,存放了100H个16位...

Global site tag (gtag.js) - Google Analytics