Page 1 of 3 123 LastLast
Results 1 to 25 of 102

Thread: array

Hybrid View

Previous Post Previous Post   Next Post Next Post
  1. #1
    Eclipse Plugin Developer aphex's Avatar
    Join Date: Mar:2003
    Location: Karlsruhe
    Posts: 546

    array

    ,
    O(logn).
    ( 1 n-1) 1 n. .. .
    array e :

    [1,2,4,5,6,7,8] 3.

    " /", . , , .

    Big O-Notation

    .
    We are drowning in information, but starving for knowledge and time!

  2. #2
    philosophus duratea icaci's Avatar
    Join Date: Oct:2006
    Location: Aachen
    Posts: 2,698
    ( 1) :
    - 0 , -
    - 1 , -

    b[i] = a[i] - i ( ):
    a[1,2,4,5,6,7,8] -> b[0,0,1,1,1,1,1]
    , b[i] 0 1. O(log n) .

    O(log n) " ".
    Internet - it doesn't make you stupid, it just makes your stupidity more accessible to others

  3. #3
    Eclipse Plugin Developer aphex's Avatar
    Join Date: Mar:2003
    Location: Karlsruhe
    Posts: 546
    icaci, . . (n), a . , .
    We are drowning in information, but starving for knowledge and time!

  4. #4
    Pesho's Avatar
    Join Date: Nov:2001
    Location: Sofia
    Posts: 5,169
    Quote Originally Posted by aphex View Post
    icaci, . . (n), a . , .

    . , - , .

  5. #5
    Defender Kaspirtov's Avatar
    Join Date: Jun:2006
    Location: Sf
    Posts: 7,414
    Quote Originally Posted by aphex View Post
    ,
    O(logn).
    ( 1 n-1) 1 n. .. .
    array e :

    [1,2,4,5,6,7,8] 3.

    " /", . , , .

    Big O-Notation

    .
    ... array n-1 , , , rry[indx] > indx+1 . .. :
    Code:
    int missingNumber;
    for(int i = 0; i <= n-1; i++)
    {
        if(arry[i] > i+1)
       {
           missingNumber = i+1;
           break;
       }
    }
    "-" ? ... .

    : submit-a..... ...
    " , , , , ."

  6. #6
    philosophus duratea icaci's Avatar
    Join Date: Oct:2006
    Location: Aachen
    Posts: 2,698
    @aphex, b . , Pesho(R), . C , 0:
    Code:
    int missing(int a[], int n)
    {
      int low = 0, high = n-1;
      do
      {
        int mid = (low+high) / 2;
        if (a[mid] > mid+1)
          high = mid;
        else
          low = mid;
      } while (high-low > 1);
      return(high+1);
    }
    Internet - it doesn't make you stupid, it just makes your stupidity more accessible to others

  7. #7
    Eclipse Plugin Developer aphex's Avatar
    Join Date: Mar:2003
    Location: Karlsruhe
    Posts: 546
    , . ..

    .. 1 n . .

    , , . , .
    Last edited by aphex; 15th May 2008 at 01:46.
    We are drowning in information, but starving for knowledge and time!

  8. #8
    .... thedivaka's Avatar
    Join Date: Mar:2006
    Location: 8.3
    Posts: 4,951
    , ?

    ? 2 , - , - - , , a(i)=i, ( , , ) . , . - - - , .
    , ,
    , , .

  9. #9
    Eclipse Plugin Developer aphex's Avatar
    Join Date: Mar:2003
    Location: Karlsruhe
    Posts: 546
    . , icaci. n, . :
    Code:
    static int missing(int a[])
    {
      int low = 0, high = a.length;
      do
      {
        int mid = (low+high) / 2;
        if (a[mid] > mid+1)
          high = mid;
        else
          low = mid;
      } while (high-low > 1);
      return(high+1);
    }
    }

    . , , .
    " . - array, . , [i][k] k- i- . , O(n) array ."

    , array, . . O(n^2).


    :@thedivaka,a . . icaci,Pesho, anrieff Kaspirtov
    Last edited by aphex; 15th May 2008 at 10:07.
    We are drowning in information, but starving for knowledge and time!

  10. #10
    .... thedivaka's Avatar
    Join Date: Mar:2006
    Location: 8.3
    Posts: 4,951
    ,

    - () , ?

    - - .
    , , n-1, 1 n, , .

  11. #11
    Pesho's Avatar
    Join Date: Nov:2001
    Location: Sofia
    Posts: 5,169
    Quote Originally Posted by aphex View Post
    , array, . . O(n^2).

    - O(n^2). n (O(n)), (8). ( O(n)), , anrieff, . , , .

  12. #12
    ɐ-əpoɔᴉu⋂ ɐ ə anrieff's Avatar
    Join Date: Apr:2004
    Location: Sofia
    Posts: 8,448
    , ((1)) .
    len(a)*(len(a)+1)/2 - sum(a),
    , . .
    "640K ught to be enough for anybody" - Bill Gates, 1981
    ::Machine specs::Fract::AGG::::Baileys::blog::YouTube channel

  13. #13
    philosophus duratea icaci's Avatar
    Join Date: Oct:2006
    Location: Aachen
    Posts: 2,698
    @aphex, C ( C++ ). "", .
    Internet - it doesn't make you stupid, it just makes your stupidity more accessible to others

  14. #14
    Eclipse Plugin Developer aphex's Avatar
    Join Date: Mar:2003
    Location: Karlsruhe
    Posts: 546
    , java, .

    , ( ). , .

    :
    { {0,0,1}, = 1
    {0,0,0}, = 0
    {0,1,0}, = 2
    {1,0,0}, = 4 .
    {1,0,1},
    {1,1,0},
    {1,1,1}}
    , copy/paste Java.
    We are drowning in information, but starving for knowledge and time!

  15. #15
    The Conquerer I Be RazorJack's Avatar
    Join Date: Jul:2001
    Location:
    Posts: 3,108
    quicksort .... ( ) . ...

  16. #16
    .... thedivaka's Avatar
    Join Date: Mar:2006
    Location: 8.3
    Posts: 4,951
    . , - .

    , 2, . . , . N-1 M , 1 N ( ), 2
    {0,0,1}, = 1
    {0,0,0}, = 0
    {0,1,0}, = 2
    {1,0,0}, = 4
    {1,0,1},
    {1,1,0},
    {1,1,1}
    N ( , , 0 1) .
    - ( , ) ?

  17. #17
    Eclipse Plugin Developer aphex's Avatar
    Join Date: Mar:2003
    Location: Karlsruhe
    Posts: 546
    , , .

    Quicksort - (n^2), . -. , O(n^2). , , .

    :
    http://en.wikipedia.org/wiki/Sorting_algorithm
    We are drowning in information, but starving for knowledge and time!

  18. #18
    .... thedivaka's Avatar
    Join Date: Mar:2006
    Location: 8.3
    Posts: 4,951
    , ( )

    ? - 20 , 20 .
    O(N^2) O(N*M)
    - ,
    - 10 20 - .

    "" , -.
    , .

  19. #19
    ɐ-əpoɔᴉu⋂ ɐ ə anrieff's Avatar
    Join Date: Apr:2004
    Location: Sofia
    Posts: 8,448
    "" , -. -, ((N) (N logN) + binsearch)
    , . .
    "640K ught to be enough for anybody" - Bill Gates, 1981
    ::Machine specs::Fract::AGG::::Baileys::blog::YouTube channel

  20. #20
    philosophus duratea icaci's Avatar
    Join Date: Oct:2006
    Location: Aachen
    Posts: 2,698
    Anrieff: " , , n*(n-1)/2 " O(n), .
    Internet - it doesn't make you stupid, it just makes your stupidity more accessible to others

  21. #21
    no brain no pain baracuda's Avatar
    Join Date: Aug:2006
    Location: Sofia
    Posts: 35,840
    " ". swap- ? - - .
    . ( Quick Sort), , . Merge sort . - . .

  22. #22
    Eclipse Plugin Developer aphex's Avatar
    Join Date: Mar:2003
    Location: Karlsruhe
    Posts: 546
    . :
    (, ) 2 000 000 . :

    ------
    QSort: 749 ms
    QSort: 337 ms
    ------
    QSort: 280 ms
    QSort: 323 ms
    --- ---
    QSort: 274 ms
    QSort: 265 ms
    We are drowning in information, but starving for knowledge and time!

  23. #23
    The Conquerer I Be RazorJack's Avatar
    Join Date: Jul:2001
    Location:
    Posts: 3,108
    quick sort ? 10 ?

    merge sort-a , ?

  24. #24
    Eclipse Plugin Developer aphex's Avatar
    Join Date: Mar:2003
    Location: Karlsruhe
    Posts: 546
    , , ... Merge Sort . , , ..

    . 2 000 000 274 , . ... 270 .

    , :
    Code:
    public static int generateNumber(int left, int right){
    	int m=0;
    	do { 
    	  m = (int)(Math.random()*right + left);
    	}while((m>right) || (m<left));
    	
    	return m;
    		
      }
    Last edited by aphex; 19th May 2008 at 16:44.
    We are drowning in information, but starving for knowledge and time!

  25. #25
    Pesho's Avatar
    Join Date: Nov:2001
    Location: Sofia
    Posts: 5,169
    Quote Originally Posted by aphex View Post
    , :

    , "" . .

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

Copyright © 1999-2011 . .
iskamPC.com | mobility.BG | Bloody's Techblog | | 3D Vision Blog |