- 浏览: 443189 次
- 性别:
- 来自: 深圳
文章分类
- 全部博客 (158)
- J2SE (15)
- c/c++ (17)
- linux & ubuntu (20)
- js (18)
- algorithm (21)
- android (1)
- software (3)
- svn (1)
- db (6)
- other (19)
- css (5)
- go (1)
- html 5 (3)
- computer science (1)
- php (3)
- 创业 (8)
- EJB & jboss (1)
- TDD (1)
- jsp & servlet (2)
- http, tcp & ip (2)
- hibernate (1)
- json (1)
- 乐 (2)
- ps (2)
- netbeans (1)
- extjs (2)
- eclipse (4)
- 项目管理 (1)
- varnish (2)
- study abroad (1)
- python (1)
- erlang (1)
- math (1)
- shell (1)
- assembly (4)
- lucene (1)
- web (1)
- http (1)
- tcp & ip (1)
最新评论
-
yiguxianyun:
...
css li 不换行 -
stdayong:
...
netbeans 中使用 maven -
程序猿_星:
为啥会中文乱码啊
servlet 以 gzip 格式返回数据 -
huanhuan519:
感谢分享~
gdb 调试工具 -
heyl1234:
写过些js,对css还不熟。谢谢~
css li 不换行
已排序数组 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; } }
发表评论
-
c - linkedlist
2012-05-10 14:52 1081c - linkedlist store ordere ... -
c - word counter (binary-tree)
2012-05-09 14:17 1726c - word counter (binary-tree) ... -
random select
2011-08-28 01:00 1205random select problem: ... -
sparse data structure - matrix
2011-08-18 20:03 1083sparse data structure sp ... -
max sub_sequence - c
2011-08-10 01:02 1074max sub_sequence - c /* ... -
binary search - c
2011-08-06 12:07 1092binary search - c (simple) ... -
bit_array - simple use
2011-05-28 23:47 1007bit array,use less memory to de ... -
linkedlist - java 简单实现
2011-02-11 21:29 1593linked list 链表, - ... -
queue (用 java 简单实现)
2011-02-03 01:45 4048queue ------ 结构 线性存 ... -
Medians and Order Statistics (次序统计)
2011-01-03 14:36 2828Medians and Order Statistics - ... -
counting sort
2011-01-02 20:36 1564counting sort ------ counting ... -
quick sort
2011-01-01 20:26 1191quicksort ------ quicksort ove ... -
priority queue
2010-12-22 00:11 2270priority queue priority queue ... -
heap sort
2010-12-18 19:09 1206heapsort ------ heap 数据结构 hea ... -
merge sort
2010-12-01 23:37 1150merge sort 合并排序 ------ merge ... -
insertion sort
2010-10-28 00:21 1044insertion sort ------ insertio ... -
z 字型 读取 矩阵
2010-10-23 16:50 2190以 z 字型 读取 矩阵, ... -
排序算法:求 长度为 n的 数组中,最大的 m个数
2010-08-31 10:16 2632排序:数组 length=m,从其中中取出最大的 n 数字,n ... -
binary search
2010-08-29 19:35 973binary search in sorted array: ... -
An Introduction to Algorithm 2nd 's contents
2010-08-11 23:02 1185算法导论(2nd) 结构 * <Introductio ...
相关推荐
这个关系意味着,对于任何特征向量x,矩阵A乘以其自身的结果的范数(即Axxl)等于λ乘以x的范数的平方(xxl),而这里提到的范数是矩阵的行范数,即矩阵每一行元素绝对值之和的最大值。 当我们讨论特征值小于11的...
在Java编程语言中,解决这个问题的方法多种多样,但这里提到的思路是通过逐步比较数组中的元素来找到最大值。这种方法被称为线性搜索,因为它的复杂度与数组的长度成正比。 首先,我们需要理解数组的基本概念。数组...
首先对数组进行排序,然后计算排序后数组中最大值与最小值之间的差,这个差即为所求的最大值。 #### 代码解析 在给定的部分代码中,作者采用了冒泡排序算法对数组进行排序。具体实现步骤如下: 1. **初始化数组**:...
第34题,"在排序数组中查找元素的第一个和最后一个位置",是这样一类问题:它不仅测试了基本的数组操作,还涉及到二分查找的高级应用。下面我们将详细探讨这个问题以及相关的知识点。 ### 问题描述 给定一个已排序...
例如,对于数组`[-3, 1, -2, 4]`,其绝对值排序结果应为`[1, -2, -3, 4]`。 ##### 3. C++语言基础 该代码片段使用了C++语言,并包含了标准输入输出库`<iostream>`和数学函数库`<cmath>`。其中,`using namespace ...
例如,`sort(A,'ComparisonMethod','abs')`会根据元素的绝对值进行排序,而不是它们的原始值。 5. **返回索引**: `[B,I] = sort(___)` 除了返回排序后的数组`B`之外,还会返回一个索引向量`I`,`I`的大小与`A`...
//请给出一个高效的程序找出2个位置(开始和结束),使从一个A[start]到A[end]的和绝对值最大,并返回这个值(最大值)。 //例 A[5]={2,-1,4,-3,2};该数组最大和的子集合:起始位置为“0”,结束位置为“2” ,最大值为5...
3. **最大负数的查找**:编程时,我们需要遍历数组M,比较每个元素的值,找出最小的负数。由于我们要找的是最大负数的绝对值,因此实际上是在找最小的负整数。 4. **绝对值计算**:在计算机编程中,获取一个数的...
在MATLAB编程环境中,`maxabs`函数是一个非常实用的工具,用于找出向量、矩阵或数组中的最大绝对值。这个函数是MATLAB语言基础的一部分,对于数据分析、数值计算以及算法开发有着广泛的应用。现在,让我们深入探讨...
例如,`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; }
public class exercessinto { byte y; double sum;... public void juedui(byte x)//<一>byte绝对值问题 { y=(byte)Math.abs(x); System.out.println("byte类型的数字的绝对值为:"+y); }
2. **冒泡排序法**:冒泡排序是一种简单的排序算法,它通过不断交换相邻的两个元素来逐步排序数组。在这个例子中,定义了一个整数数组`a`,然后使用两个嵌套循环,外层循环控制比较的趟数,内层循环进行两两比较并...
`Function`是过程的一种,它可以返回一个值给调用它的语句。这与`Sub`过程不同,`Sub`过程只执行一系列操作,但不返回任何值。下面是一个简单的`Function`定义的例子: ```vb Function 绝对值(ByVal 数字 As Double...
在编程和算法设计中,"数组输出1" 这个问题是一个典型的数组处理任务,它涉及到查找数组中的最大绝对值元素以及返回其对应的下标。这个问题可以被看作是线性搜索的一种特殊情况,因为我们需要遍历整个数组来找到具有...
假设我们有一个整数数组,我们希望按照元素的绝对值大小进行排序,可以创建如下的比较器类: ```java import java.util.Comparator; public class AbsValueComparator implements Comparator<Integer> { @...
本文将深入探讨如何在C++中实现数组和容器的排序,并涵盖几种不同的排序算法。 首先,对于基本类型的数组,C++标准库提供了一个非常方便的函数`std::sort`,它位于`<algorithm>`头文件中。例如,如果你有一个整数数...
初一数学压轴题绝对值化简求值。 本资源内容涵盖了初一数学压轴题中的绝对值化简求值知识点,包括绝对值的代数意义、绝对值化简、有理数运算、平方和绝对值的非负性、二元一次方程组等。 一、初一数学压轴题:...
6. **求两个有序数组的共同元素**: 对于两个有序数组,可以采用双指针法,分别从头开始比较,找到相同的元素。 7. **求三个数组的共同元素**: 可以先找出两个数组的交集,再找这个交集与其他数组的交集。 8. *...
5.15 数据段中已定义了一个有N个字数据的数组M,试编写一程序求出M中绝对值最大的数,把它放在数据段的M+2n单元中,并将该数的偏移地址存放在M+2(n+1)单元中。 5.16 在首地址为DATA的字数组中,存放了100H个16位...