生活随笔
收集整理的這篇文章主要介紹了
最小可用ID
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
描述
在非負(fù)數(shù)（亂序）中找到最小的可分配的id（從1開始編號(hào)），數(shù)據(jù)量1000000；
輸入
第一行 數(shù)組長(zhǎng)度
輸出
整數(shù)
樣例輸入
5
樣例輸出
6
解題思路
static int f ( int [ ] arr
) { int i
= 1 ; while ( i
< arr
. length
) { if ( indexof ( arr
, i
) == - 1 ) { return i
; } }
}
static int indexof ( int [ ] arr
, int k
) { for ( int i
= 0 ; i
< arr
. length
; i
++ ) { if ( arr
[ i
] == k
) return 1 } return - 1 ;
}
解法二:
static int f ( int arr
) { int [ ] help
= new int [ arr
. length
+ 1 ] ; for ( int i
= 0 ; i
< arr
. length
; i
++ ) { if ( arr
[ i
] < help
. length
) { help
[ arr
[ i
] - 1 ] = 1 } } for ( int i
= 0 ; i
< help
. length
; i
++ ) { if ( help
[ i
] == 0 ) { return i
+ 1 ; } } return help
. length
+ 1 ;
}
解法三：
static int f ( int [ ] arr
) { Arrays
. Sort ( arr
) ; for ( int i
= 0 ; i
< arr
. length
; i
++ ) { if ( arr
[ i
] != i
+ 1 ) { return i
+ 1 ; } }
}
解法四：
static int f ( int [ ] arr
) { Arrays
. Sort ( arr
) ; return p ( arr
, 0 , arr
. length
- 1 ) ;
}
static int p ( int [ ] arr
, int begin
, int end
) { if ( begin
<= end
) { int indexMid
= ( begin
+ end
) >> 1 ; if ( arr
[ indexMid
] == indexMid
+ 1 ) { return p ( arr
, indexMid
+ 1 , end
) } else { return p ( arr
, begin
, indexMid
- 1 ) ; } } return begin
+ 1 ;
}
總結(jié)
以上是生活随笔 為你收集整理的最小可用ID 的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔 推薦給好友。
