對從0到1的所有整數進行數組檢查

這裏是問題：我的程序獲取一個大小爲n的數組，其中包含從0到n-1的數字。你可以假設我們沒有得到低於0的數字或高於n-1的數字。對從0到1的所有整數進行數組檢查

我需要檢查數組是否包含0到n-1之間的所有數字，如果是，則返回1。否則爲0。

您不允許使用其他數組，並且程序必須在O（n）中運行。

例子：4,1,0,3,2返回1.

數組大小5：

大小5的陣列4,1,0,3,1返回0（ 2不在陣列中）

嘗試以服務方式卡住任何幫助將不勝感激。

來源

2016-01-04 barmash

這是一個提示：如果在所有需要的值都存在時總結所有值，您會得到什麼結果？ – Hogan

@Hogan sum（0,1,2,3,4）= sum（0,0,3,3,4）= 10 – BLUEPIXY

如果我總結所有值我可以得到一些數組相同的乘積所有值false postive。 – barmash

讓我們假設2的補碼int，並且可以更改數組。使用符號位來標記訪問過的單元格。

輕輕測試代碼

int OneOfEach(int *A, int count) { 
    int result = 1; 
    for (int i = 0; i < count; i++) { 
    int cell_to_mark = A[i]; 
    if (cell_to_mark < 0) { 
     cell_to_mark = -1 - cell_to_mark; 
    } 
    assert(cell_to_mark >= 0 && cell_to_mark < count); 
    if (A[cell_to_mark] < 0) { 
     // done all ready 
     result = 0; 
     break; 
    } 
    A[cell_to_mark] = -1 - A[cell_to_mark]; 
    } 
    // restore. 
    for (int i = 0; i < count; i++) { 
    if (A[i] < 0) { 
     A[i] = -1 - A[i]; 
    } 
    } 
    return result; 
}

來源

2016-01-04 21:55:39 chux

請注意，在二進制補碼系統中，'-1 - x'只是'〜x'。 –

@Tom Karzes關於'-1 - x'只是'〜x'。我傾向於只編碼位運算符'〜＆|^>><<與無符號類型。這樣可以減少麻煩。 – chux

@chux你將會與Java有一段不愉快的時光;） –

這可以用類似的特殊週期排序東西值0到n-1來完成。時間複雜度是O（n）。

/* check if a[] has one each of numbers 0 to n-1 */ 
/* reorder a[] in place according to values in a[] */ 
/* a[] only has numbers 0 to n-1 */ 
/* also sorts array in O(n) time */ 
int chka(int a[], int n) 
{ 
int i, j, k; 
    for(i = 0; i < n; i++){ 
     if(i != a[i]){     /* if element out of place */ 
      k = i;      /* cycle elements */ 
      while(i != (j = a[k])){ 
       if(a[k] == k)   /* if destination already has */ 
        return 0;   /* value, it's a duplicate */ 
       a[k] = k; 
       k = j; 
       if(k < 0 || k >= n)  /* if out of range */ 
        return 0;   /* return 0 */ 
      } 
      if(a[k] == k)    /* if destination already has */ 
       return 0;    /* value, it's a duplicate */ 
      a[k] = k; 
     } 
    } 
    return 1; 
}

來源

2016-01-05 02:56:54 rcgldr

你只是把每個元素放在它所屬的位置。如果有兩個屬於同一個地點，那麼你有一個副本，這意味着必須丟失一個。

bool checkArray(int *array, int count) 
{ 
    int i=0; 
    while (i<count) 
    { 
     int el = array[i]; 
     if (el < 0 || el >=count) 
      return false; 
     if (el == i) 
     { 
      //already in the right place 
      ++i; 
      continue; 
     } 
     if (array[el]==el) 
      return false; //duplicate 
     //swap element into correct position 
     array[i]=array[el]; 
     array[el]=el; 
     //loop to reprocess the same position, since we just 
     //changed the element there 
    } 
    return true; 
}

來源

2016-01-05 03:10:35

對從0到1的所有整數進行數組檢查

回答

相關問題