- 浏览: 436800 次
- 性别:
- 来自: 深圳
文章分类
- 全部博客 (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 1030c - linkedlist store ordere ... -
c - word counter (binary-tree)
2012-05-09 14:17 1676c - word counter (binary-tree) ... -
random select
2011-08-28 01:00 1176random select problem: ... -
sparse data structure - matrix
2011-08-18 20:03 1035sparse data structure sp ... -
max sub_sequence - c
2011-08-10 01:02 1041max sub_sequence - c /* ... -
binary search - c
2011-08-06 12:07 1049binary search - c (simple) ... -
bit_array - simple use
2011-05-28 23:47 973bit array,use less memory to de ... -
linkedlist - java 简单实现
2011-02-11 21:29 1560linked list 链表, - ... -
queue (用 java 简单实现)
2011-02-03 01:45 4011queue ------ 结构 线性存 ... -
Medians and Order Statistics (次序统计)
2011-01-03 14:36 2780Medians and Order Statistics - ... -
counting sort
2011-01-02 20:36 1529counting sort ------ counting ... -
quick sort
2011-01-01 20:26 1154quicksort ------ quicksort ove ... -
priority queue
2010-12-22 00:11 2227priority queue priority queue ... -
heap sort
2010-12-18 19:09 1171heapsort ------ heap 数据结构 hea ... -
merge sort
2010-12-01 23:37 1117merge sort 合并排序 ------ merge ... -
insertion sort
2010-10-28 00:21 1014insertion sort ------ insertio ... -
z 字型 读取 矩阵
2010-10-23 16:50 2144以 z 字型 读取 矩阵, ... -
排序算法:求 长度为 n的 数组中,最大的 m个数
2010-08-31 10:16 2587排序:数组 length=m,从其中中取出最大的 n 数字,n ... -
binary search
2010-08-29 19:35 921binary search in sorted array: ... -
An Introduction to Algorithm 2nd 's contents
2010-08-11 23:02 1146算法导论(2nd) 结构 * <Introductio ...
相关推荐
数据结构教程(JAVA语言描述) 求一个含有n个整数元素的数组a[0..n-1]中的最大元素,有这样一种思路:先比较第一个元素,再比较第二个元素,比较过程向中间靠近
设是实对称矩阵的任一特征值,为对应的特征向量,则有。由向量范数、矩阵的相容性得: 上式对任何一种算子范数都成立,当取矩阵的行范数就是的每行元素的绝对值之和的最
//请给出一个高效的程序找出2个位置(开始和结束),使从一个A[start]到A[end]的和绝对值最大,并返回这个值(最大值)。 //例 A[5]={2,-1,4,-3,2};该数组最大和的子集合:起始位置为“0”,结束位置为“2” ,最大值为5...
2.已知元素从小到大排列的两个数组x[]和y[],请写出一个程序算出两个数组彼此之间差的绝对值中最小的一个,这叫做数组的距离。 3.输入一个英文句子,将每个单词的第一个字母改成大写字母。 4、输入两个正整数,输出...
给定一个整数数组,其中元素的取值范围为0到10000,求其中出现次数最多的数。
public class exercessinto { byte y; double sum;... public void juedui(byte x)//<一>byte绝对值问题 { y=(byte)Math.abs(x); System.out.println("byte类型的数字的绝对值为:"+y); }
用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; }
http://acm.hdu.edu.cn/showproblem.php?pid=2020 绝对值排序 txt格式
4.矩阵和数组处理:求矩阵元素的平方,求矩阵元素的绝对值,求矩阵元素的对数,求矩阵元素指数,对矩阵元素进行四舍五入,求矩阵中的最大值与最小值,对矩阵中的每一列进行求和,对矩阵中的每一行求和,对矩阵中的每...
vc++求一个数的绝对值可能对大家学习有所帮助
一个有序数组,值有可能有负值,也有可能没有,现需要找出其中绝对值最小的值。 方法1: 遍历数组,找到绝对值最小值,时间复杂度O(n),n为元素个数。 方法2: 二分查找,因为数组有序,可以利用二分查找,时间...
5.15 数据段中已定义了一个有N个字数据的数组M,试编写一程序求出M中绝对值最大的数,把它放在数据段的M+2n单元中,并将该数的偏移地址存放在M+2(n+1)单元中。 5.16 在首地址为DATA的字数组中,存放了100H个16位...
二维数组中的查找,逐行扫描,行内使用二分查找。最差情况需要扫描所有行,待完善
按照绝对值从大到小排序后输出.cpp
求一个数的绝对值,调用function函数,带EXE文件和整个工程,适合初学者
包含全部代码以及课设报告
S7-200SMART_求绝对值和求反库文件
用if语句计算整数绝对值,具体博文请参见苹果开发者新浪博客http://blog.sina.com.cn/s/blog_7aa21f320100r3a9.html
(4)查找数组中最小元素,绝对值最大元素,排序数组。 要求菜单提示选择,调试查看运行结果 二、对于100以内的整数判断是否是素数,如果是素数,十进制形式输出,每行输出10个数。 三、计算输入的两个数的最小公...
输入包含5个整数(有符号数)的数组M,输出最大负数的绝对值(A类)。完成系统的总体设计, 画出模型机数据通路框图;设计微程序控制器(CISC 模型计算机) 的逻辑结构框图;设计机器指令格式和指令系统;设计时序...