Sorted array a, demand the absolute value of its elements the total number of different values

2010-08-29  来源:本站原创  分类:Tech  人气:149 

Sorted array a, demand the absolute value of its elements the total number of different values?

Ideas:

2 index, from 0 to 2 elements closest to the two side began to traverse, each time compare the two index elements where the absolute value, minimum value, and compare the final value of 1 if greater than, then count + + and the value is set to last value, then small forward direction of the index plus 1,

Algorithm complexity:

As long as the traverse 1, the complexity is o (n), n is the number of the array,

Memory footprint:

Need two index, 1 A last, 1 count, so except array, the extra memory is fixed occupation, that is o (1)

Code:

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)));
        }

        /**
         *  Get sorted array  , The absolute value of the number of different  , It is assumed that the array has  0,
         *  If the array has no other 0 can write methods to find the nearest  0 Number 2 of    Index of, and slightly modified by method   count  Value to initialize  ,
         * @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;
        }
}
相关文章
  • Sorted array a, demand the absolute value of its elements the total number of different values 2010-08-29

    Sorted array a, demand the absolute value of its elements the total number of different values? Ideas: 2 index, from 0 to 2 elements closest to the two side began to traverse, each time compare the two index elements where the absolute value, minimum

  • Remove an already sorted array repeat the figures 2010-12-21

    / * * Get rid of an already sorted array repeat the figures, as fast as * Enter a = {1,1,3,5,5,7,9} * Output b = {1,3,5,7,9} * / # Include <stdio.h> int delSameValues (int * a, int n) { int i; int j = 0; for (i = 0; i <n; i + +) { if (i == 0) { *

  • [leetcode] Remove Duplicates from Sorted Array 2013-08-21

    Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory. For example, Given input array A =

  • [leetcode] Search in Rotated Sorted Array 2014-06-25

    Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e.,0 1 2 4 5 6 7might become4 5 6 7 0 1 2). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate

  • Turn - by-bit computing demand the absolute value of integer 2010-03-29

    MOV EDX, EAX; SAR EDX, 31; / / if EAX is negative: EDX = oxffffffff, otherwise EDX = 0 XOR EAX, EDX; / / if EAX is negative: EAX to take anti-, or EAX unchanged SUB EAX, EDX; / / if EAX is negative: EAX by 0xffffffff (-1) plus 1 is the absolute negat

  • Merge Sorted Array 2014-04-22

    to be continue

  • Get the absolute position of page elements 2010-10-14

    Absolute position mentioned here refers to an element of the page relative to the upper left corner of the coordinates. If an element has been defined position: absolute; the style, then its left / top are specified, may be obtained directly. Most of

  • Absolute positioning of block elements margin properties 2010-11-28

    For absolutely positioned div's margin has been thought that property is valid only through the top, left, bottom, right orientation, but today only to find that not the case, so do some of their experiment: The original test file using HTML: <!DOCTY

  • VB ListBox instead of the array can be used to quickly find a value of index number 2010-03-26

    For example: To find the "hbwl" cited by the index number of the ListBox1.Text = "hbwl" syh = ListBox1.ListIndex msgbox (syh)

  • transfer java application jcom to word pdf 2010-04-14

    1. Java application jcom will transfer pdf word 2. 3. Experience 2009 - 03 - 01 09: 47 to read 528 comments 0 4. Font size: much of the small 5. In JAVA using JCOM and JXL tips: 6. 7. (1) should be under your lib jdom-1.0. Jar, jxl-2.5. 5. Jar, jcom-

  • javascript in Math.random () to use 2010-09-24

    Math.random () method returns the range of random number between 0 and 1, excluding 0 and 1: Using Math.random () to obtain a range of values: Value = Math.floor (Math.random () * + the total number of possible values of the first possible value) As

  • javascript in Math.random () use 2010-09-24

    Math.random () method returns the range of random number between 0 and 1, excluding 0 and 1: Use Math.random () to obtain a range of values: Value = Math.floor (Math.random () * + the total number of possible values of the first possible value) As fo

  • ssh + mysql large field treatment 2011-09-19

    Large field is divided into two, one clob, that is a long text. Usually used to store more than a certain number (eg 4000) character, one blob, the binary bytes of data, usually user-submitted attachment is assumed ssh + mysql development environment

  • Kadane's Algorithm to find maximum subarray sum 2013-04-29

    Given an array of n integers (both +ve and -ve). Find the contiguous sub-array whose sum is maximum (More than 1 sub-array may have same sum). For Example: Array Maximum Sub-Array sum ----------------------- ----------------------- ---- {5, 7, 12, 0,

  • GSUB - Glyph置换表 2013-07-04

    Glyph置换表(GSUB)包含了用于置换glyphs以便于渲染字库中的script和language system的信息.许多language systems都需要glyph置换.比如,在Arabic script中,描画了一个特定字符的glyph形状会依据于它在单词或字串中的位置而改变(参见figure 1).在其他的一些language systems中,glyph置换则是用户的一种审美上的选项,比如,在English语言中连字glyphs的使用(参见Figure 2). Figure 1

  • GPOS - Glyph定位表 2013-07-14

    Glyph定位表(GPOS)为一个字库所支持的每种script和language system里复杂的文本布局及渲染提供了关于glyph 放置的精确的控制. 概览 复杂的glyph定位在一些书写系统中变成了一个问题,比如Vietnamese,它使用了diacritical和其他的marks来改变字符的读音或意义.为了易读性及语言上的精确,这些书写系统需要控制所有的marks彼此之间的放置. Figure 4a. Vietnamese words with marks. 其他的书写系统为了正确的排

  • Java array with the container class analysis 2010-03-29

    When reading a problem thinking for java in the array and list what kind of difference? An article on the Internet is to share the next. http://tech.e800.com.cn/articles/2009/98/1252373217457_1.html Array is a Java-built-in types, In addition, Java h

  • A detailed comparison of an array of containers 2010-03-29

    1, Array, Arrays Java all the "random access storage and a series of objects" approach, array is the most efficient kind. 1, High efficiency, but the capacity of the fixed and can not be changed dynamically. array there is a drawback is that the

  • JS ARRAY Array Operations 2009-11-12

    The recent use of the Array on them a finishing, the contents of the text to read the article excerpt others add their own operation by experiment, not entirely original. The three properties of the array object 1, length attribute length property Le

  • Collection and Collections: Array and Arrays difference 2010-03-24

    Collection and the Collections of the differences: Collection is under java.util interface, it is the structure of the parent interface to a variety of collections. Interface inheritance and his main Set and List. Collections is dedicated under the j