整数の連続範囲があるとしましょう。ここ[0, 1, 2, 4, 6]で、3は最初の「欠落している」数です。この最初の「穴」を見つけるためのアルゴリズムが必要です。範囲が非常に大きい（おそらく2^32エントリを含む）ため、効率が重要です。数値の範囲はディスクに保存されます。スペース効率も主な関心事です。
時間とスペースを効率的に使用するのに最適なアルゴリズムは何ですか？
質問する
22618 次
16 に答える
40
二分探索を使用します。数値の範囲に穴がない場合、範囲の終了と開始の差は、範囲内のエントリの数にもなります。
したがって、数字のリスト全体から始めて、前半にギャップがあるかどうかに基づいて、前半または後半のいずれかを切り落とすことができます。最終的には、中央に穴のある2つのエントリがある範囲に到達します。
これの時間計算量はですO(log N)。最悪の場合がである線形スキャンとは対照的ですO(N)。
于 2012-07-08T19:16:33.827 に答える
6
上記の @phs によって提案されたアプローチに基づいて、これを行う C コードを次に示します。
#include <stdio.h>
int find_missing_number(int arr[], int len) {
int first, middle, last;
first = 0;
last = len - 1;
middle = (first + last)/2;
while (first < last) {
if ((arr[middle] - arr[first]) != (middle - first)) {
/* there is a hole in the first half */
if ((middle - first) == 1 && (arr[middle] - arr[first] > 1)) {
return (arr[middle] - 1);
}
last = middle;
} else if ((arr[last] - arr[middle]) != (last - middle)) {
/* there is a hole in the second half */
if ((last - middle) == 1 && (arr[last] - arr[middle] > 1)) {
return (arr[middle] + 1);
}
first = middle;
} else {
/* there is no hole */
return -1;
}
middle = (first + last)/2;
}
/* there is no hole */
return -1;
}
int main() {
int arr[] = {3, 5, 1};
printf("%d", find_missing_number(arr, sizeof arr/(sizeof arr[0]))); /* prints 4 */
return 0;
}
于 2014-03-29T20:10:40.537 に答える
4
0 からn - 1 までの数値が配列内でソートされるため、最初の数値はそれらのインデックスと同じである必要があります。つまり、番号 0 はインデックス 0 のセルに配置され、番号 1 はインデックス 1 のセルに配置されます。欠落している数がmとして示されている場合。m未満の数値は、値と同じインデックスを持つセルに配置されます。
数値m + 1 はインデックスmのセルに配置され、数値m + 2 はインデックスm + 1 のセルに配置されます。欠損値mは、値がその値と同一でない最初のセルであることがわかります。
したがって、配列を検索して、値がその値と同一でない最初のセルを見つける必要があります。配列はソートされているため、以下に実装されている二分探索アルゴリズムに基づいて O(lg n ) 時間で見つけることができます。
int getOnceNumber_sorted(int[] numbers)
{
int length = numbers.length
int left = 0;
int right = length - 1;
while(left <= right)
{
int middle = (right + left) >> 1;
if(numbers[middle] != middle)
{
if(middle == 0 || numbers[middle - 1] == middle - 1)
return middle;
right = middle - 1;
}
else
left = middle + 1;
}
return -1;
}
このソリューションは、私のブログ ( http://codercareer.blogspot.com/2013/02/no-37-missing-number-in-array.html ) から借用しています。
于 2013-02-04T08:04:13.967 に答える
1
ランレングスエンコーディングを検討しましたか？つまり、最初の番号とそれに続く番号の数をエンコードします。この方法で非常に効率的に使用される数値を表すことができるだけでなく、最初のホールは最初のランレングスエンコードされたセグメントの終わりになります。
あなたの例で説明するために：
[0, 1, 2, 4, 6]
次のようにエンコードされます：
[0:3, 4:1, 6:1]
ここで、x：yは、行のy個の数に対してxから連続して始まる数のセットがあることを意味します。これにより、最初のギャップがロケーション3にあることがすぐにわかります。ただし、割り当てられたアドレスが範囲全体にランダムに分散されていない場合は、割り当てられたアドレスがクラスター化されていると、はるかに効率的であることに注意してください。
于 2012-07-08T19:15:36.157 に答える
0
リストがソートされている場合は、リストを反復処理して、次の Python コードのようにします。
missing = []
check = 0
for n in numbers:
if n > check:
# all the numbers in [check, n) were not present
missing += range(check, n)
check = n + 1
# now we account for any missing numbers after the last element of numbers
if check < MAX:
missing += range(check, MAX + 1)
多くの数値が欠落している場合は、@Nathan のランレングス エンコーディングの提案をmissingリストに使用することをお勧めします。
于 2012-07-08T19:28:54.123 に答える
0
Array: [1,2,3,4,5,6,8,9]
Index: [0,1,2,3,4,5,6,7]
int findMissingEmementIndex(int a[], int start, int end)
{
int mid = (start + end)/2;
if( Math.abs(a[mid] - a[start]) != Math.abs(mid - start) ){
if( Math.abs(mid - start) == 1 && Math.abs(a[mid] - a[start])!=1 ){
return start +1;
}
else{
return findMissingElmementIndex(a,start,mid);
}
}
else if( a[mid] - a[end] != end - start){
if( Math.abs(end - mid) ==1 && Math.abs(a[end] - a[mid])!=1 ){
return mid +1;
}
else{
return findMissingElmementIndex(a,mid,end);
}
}
else{
return No_Problem;
}
}
于 2013-08-12T22:26:59.690 に答える
0
ない
Number=(1/2)(n)(n+1)-(Sum of all elements in the array)
nのサイズはこちらarray+1。
于 2012-11-18T18:49:06.400 に答える
-1
ソートされたリストで欠落している番号を見つけるためのアルゴリズムを 1 つ取得しました。その複雑さは logN です。
public int execute2(int[] array) {
int diff = Math.min(array[1]-array[0], array[2]-array[1]);
int min = 0, max = arr.length-1;
boolean missingNum = true;
while(min<max) {
int mid = (min + max) >>> 1;
int leftDiff = array[mid] - array[min];
if(leftDiff > diff * (mid - min)) {
if(mid-min == 1)
return (array[mid] + array[min])/2;
max = mid;
missingNum = false;
continue;
}
int rightDiff = array[max] - array[mid];
if(rightDiff > diff * (max - mid)) {
if(max-mid == 1)
return (array[max] + array[mid])/2;
min = mid;
missingNum = false;
continue;
}
if(missingNum)
break;
}
return -1;
}
于 2016-03-27T08:19:28.973 に答える
-1
@phs 提供のアルゴリズムに基づく
public class Solution {
public int missing(int[] array) {
// write your solution here
if(array == null){
return -1;
}
if (array.length == 0) {
return 1;
}
int left = 0;
int right = array.length -1;
while (left < right - 1) {
int mid = left + (right - left) / 2;
if (array[mid] - array[left] != mid - left) { //there is gap in [left, mid]
right = mid;
}else if (array[right] - array[mid] != right - mid) { //there is gap in [mid, right]
left = mid;
}else{ //there is no gapin [left, right], which means the missing num is the at 0 and N
return array[0] == 1 ? array.length + 1 : 1 ;
}
}
if (array[right] - array[left] == 2){ //missing number is between array[left] and array[right]
return left + 2;
}else{
return array[0] == 1 ? -1 : 1; //when ther is only one element in array
}
}
}
于 2016-09-24T23:11:42.050 に答える
-1
public static int findFirst(int[] arr) {
int l = -1;
int r = arr.length;
while (r - l > 1) {
int middle = (r + l) / 2;
if (arr[middle] > middle) {
r = middle;
}
l = middle;
}
return r;
}
于 2019-08-11T09:38:56.640 に答える