在「無序」數組中找到數字的最佳方法？

這些數字（大部分）按順序排列。然而，起始索引處的數字可以是任意數字，並且數字是按照升序還是降序排列是未知的（數字一旦達到最小/最大數字 - 0就會迴繞，一旦達到9，反之亦然）。

其中的一個數字並不正確（就像它被拔出並隨機插入到數組中一樣）。

實施例：

[4, 3, 1, 0, 9, 8, 7, 2, 6, 5]

數2在索引7出故障。索引1和索引2之間的數字「差距」沒有問題，數字3或1也不合格。

查明無序數索引的最佳方法是什麼？

更多的例子 - 從地方數均標有*：

[2, 3, *0, 4, 5, 6, 7, 8, 9, 1] 
[5, 6, 7, 9, *8, 0, 1, 2, 3, 4] 
[7, 6, 5, 4, 3, *8, 2, 1, 0, 9] 
[0, *5, 1, 2, 3, 4, 6, 7, 8, 9] 
[4, 3, *0, 2, 1, 9, 8, 7, 6, 5]

來源

2013-05-20 Vadoff

你只需要通過數組循環，並使用一個變量來記住的號碼。如果最後一個號碼和當前號碼的差異不是1，那麼這個號碼不合格 – Raptor

這聽起來像一個有趣的求職面試問題:-) –

聽起來就像你想找到兩個不同的東西。一個是「無序」項目，另一個是「環繞」（否則可能被誤認爲是一個亂序項目）。因此，通過列表記錄差異（seq [n-1] - seq [n]> 0）的跡象並查找任何情況下，您會看到兩個連續的符號更改。一個天真的執行可能會被退化的輸入所欺騙，否則你會在線性時間內找到你的「罪魁禍首」。一個沒有錯誤的數組將會是 - ， - ， - ...，最多隻有一個變化是+，+，+ ...但是這個指針是： - ， - ， - ，+， - ，+，。 .. （或相反亦然）。 –

要查找超出序你看看陣列中的每個元素的數量。所以，你必須用複雜度O（n）迭代整個數組。

當循環通過所述陣列，則應

計算前一數字與當前數目之間的差的絕對值。
計算當前數目和下一個數

如果兩個以上的差異大於1，並且不等於n-1（當差值爲n-1，也就是之間的差的絕對值你的數組翻轉的點），那就是沒有秩序的數字。

來源

2013-05-20 02:58:15 srikanta

我認爲人們可以看到其他每個元素。 –

@ n.m。因爲任何一個元素的值都與它旁邊的元素無關，所以您需要查看每個元素。例如，如果數組是'{1,2,3,4,000,5,6,7}'，你不能只看'1,3,5,7'並且說一切都很好。 – Seph

這種方法會給你一個錯誤的肯定，因爲它們是n-2，但仍然被認爲是「按順序」，因此無論在哪裏出現亂序號碼，都會出現數字錯誤。 – Vadoff

以下人造的例子沒有獨特的解決方案。你需要決定什麼發生在這些情況下：

0, 1, 2, 3, 4, 5, 6, 7, 8, 9 // first item move to end 

2, 1, 3, 4, 5, 6, 7, 8, 9, 0 // adjacent items swapped

對於所有其他情況，幸運的是說服力的特點是，「亂序」的項目將超過1遠離都其鄰居（因爲上面的＃2）。

for (i = 0; i < arr.length; i++) { 
    int priorIndex = (i-1) % arr.length; 
    int nextIndex = (i+1) % arr.length; 
    int diffToPriorValue = abs(arr[i] - arr[priorIndex]); 
    int diffToNextValue = abs(arr[i] - arr[nextIndex]); 
    if (diffToPriorValue > arr.length/2) 
     diffToPriorValue = arr.length - diffToPriorValue; // wrap-around 
    if (diffToNextValue > arr.length/2) 
     diffToNextValue = arr.length - diffToNextValue; // wrap-around 
    if (diffToPriorValue != 1 && diffToNextValue != 1) 
     return i; 
return -1;

來源

2013-05-20 04:01:56

+1非常好的答案...相同的解決方案我看完這個問題後想出了！我特別希望你能說出兩個模棱兩可的案例（我只想到第二個案例）。給出關於如何處理這兩種情況的更多信息，您必須對第一個案例進行微小更改，對第二個案例進行更多入侵式更改，您必須確定列表的「順序」，而不會能夠使用絕對值。 –

看看每一個其他元素，並計算差異。

如果大多數差異是正數，則順序是遞增的。如果大多數都是負面的，則會下降;它可以像其他情況一樣決定，我不會再進一步檢查。

當然，你需要環繞並計算（N-1）和第0個元素之間的差異，或者其他什麼。

從現在看的diff模N

如果差異是2，這是沒有多餘或缺失的元素的正常情況下，忽略它。

如果差異爲3，元素是從某處大約這裏猛拉。但我們並不尋找它的老地方，我們正在尋找它的新地方;也忽略這一點。

如果diff是1，那麼亂序元素就在這些數字之間。

如果您有任何其他的差異，那麼你必須有兩個人彼此相鄰。亂序元素是產生這兩個差異的元素。

在兩個連續的數字的交換的情況下，任一個可以被認爲是不按順序。產生的差異將是（1,3）或（3,1）彼此相鄰。該方法選擇兩個可能的答案之一。

用於所討論的陣列：

array -> 2 3 0 4 5 6 7 8 9 1(2)   
      \/\/\/\/\/
diffs -> -2 5 2 2 -7(=3 mod 10) 
      *

在進一步的實施例I將不狀態平等模10以節省空間。

array -> 5 6 7 9 8 0 1 2 3 4(5) 
      \/\/\/\/\/
diffs -> 2 1 3 2 2 
       * 

array -> 7 6 5 4 3 8 2 1 0 9(7)   
      \/\/\/\/\/
diffs -> -2 -2 -1 -2 -3 
        * 

array -> 0 5 1 2 3 4 6 7 8 9(0)   
      \/\/\/\/\/
diffs -> 1 2 3 2 2 
      * 

array -> 4 3 0 2 1 9 8 7 6 5(4)  
      \/\/\/\/\/
diffs -> -4 -9 -3 -2 -2 
      *

更多的例子：

array -> 0 2 1 3 4 5 6 7 8 9(0)  swapped adjacent elements, case 1 
      \/\/\/\/\/
diffs -> 1 3 2 2 2 
      * 

array -> 0 1 3 2 4 5 6 7 8 9(0)  swapped adjacent elements, case 2 
      \/\/\/\/\/
diffs -> 3 1 2 2 2 
       * 

array -> 0 2 3 4 5 6 7 1 8 9(0)  element removed and inserted at odd pos 
      \/\/\/\/\/
diffs -> 3 2 2 1 2 
         * 

array -> 0 2 3 4 5 6 1 7 8 9(0)  element removed and inserted at even pos 
      \/\/\/\/\/
diffs -> 3 2 6 7 2 
        * 

array -> 0 7 1 2 3 4 5 6 8 9(0)  element removed and inserted at odd pos 
      \/\/\/\/\/
diffs -> 1 2 2 3 2 
      *    

array -> 0 1 7 2 3 4 5 6 8 9(0)  element removed and inserted at even pos 
      \/\/\/\/\/
diffs -> 7 6 2 3 2 
      *

來源

2013-05-20 05:43:59

您的算法聽起來很有趣，但我無法理解它。你介意解釋爲什麼它在問題的例子中起作用嗎？ –

@steaks：查看更新。 –

可能的編輯 - '「如果diff是2，那麼一切都很好，忽略它。如果diff是3，缺少的元素應該在這裏之間的某處，但實際的元素在別的地方，所以忽略它。我認爲你需要'[0,1,2,3,5,4,6,7,8,9]'的特例。 – Dukeling

首先我會定義什麼是「亂序」入手：

Suppose we have a list of numbers A 

If there exist A[i] in A, 
Such that A[i-1] <= A[i] <= A[i+1], then A[i] is "in order" 
Otherwise, A[i] is "out of order"

算法：

FOR i: 1..SIZE(A) DO 

    PRINT " " 
    PRINT A[i] 

    IF A[i-1] <= A[i] <= A[i+1] 
    THEN 
     CONTINUE 
    ELSE 
     PRINT "*" 
     REMOVE A[i] 
    END-IF 

END-FOR

TEST：

INPUT: { 2, 3, 0, 1, 2, 3, 5, 6, 7, 8, 9, 1 } 

OUTPUT: { 2, 3, 3, 5, 6, 7, 8, 9 } 

CONSOLE: 2 3 0* 1* 2* 3 5 6 7 8 9 1*

來源

2013-05-20 08:18:31

1）''按升序或降序排列''，所以只需'A [i-1] <= A [i] <= A [i + 1]'將不起作用。 2）每個數字只能出現一次，所以它不一定是'<='，它可以是'<'。 3）只有一個號碼處於錯誤的位置。 4）你的算法不考慮環繞。 5）對於'0,1,2,3,4,8,5,6,7,9'，你的算法將標記爲'8'和'5'，而不是'8'。 6）Eww @全部大寫。 – Dukeling

1）該算法按照給定的定義工作。 2）我將「訂單」解釋爲asc或desc命令。 3）<=或<的選擇取決於是否允許重複。 4）什麼是環繞？ 5）給定'0,1,2,3,4,8,5,6,7,9'我的算法將只標記8，因爲當8被標記時，它將從列表中被移除（忽略）。 ..感謝對我的算法的興趣，如果你討厭全部大寫，這就是我們在寫代碼時使用的方式。僞代碼 –

這是繞過：'6,7,8,9,0,1,2， 3,4,5' - 序列從中間的某處開始，一旦到達結尾，它就從頭開始。我已經看過（並且寫過）大量的僞代碼，但從來沒有全部大寫，但是，由於沒有標準，我想任何人都可以按照他們想要的方式進行操作。 – Dukeling

下面是類似Khalid的一個解決方案。

兩個元素被認爲是鄰近如果他們可以出現在彼此相鄰的無知的包裝。所以，9和0被認爲是相鄰的元素。

該算法循環通過每個組連續的三個要素，並檢查第一個和第三個相鄰與否。如果它們相鄰，則中間值必須失序。

我加入給定列表到自身，從而產生大小20的陣列這需要其中數字被轉移到開頭或列表的末尾的特殊情況的護理。

# checks if two given numbers are adjacent or not, independent of wrapping 
def adjacent?(a, b) 
    (a - b).abs == 1 || [a, b].sort == [0, 9] 
end 

# finds the misplaced number in a list 
def misplaced_number(list) 
    middle_index = 1 
    (list + list).each_cons(3).find { |first, second, third| 
    adjacent?(first, third) 
    }[middle_index] 
end

檢查以下測試。第二次也是最後一次測試失敗，因爲含糊不清。

test([2, 3, 0, 4, 5, 6, 7, 8, 9, 1], 0) 
test([5, 6, 7, 9, 8, 0, 1, 2, 3, 4], 8) # [FAIL: result = 9] 
test([7, 6, 5, 4, 3, 8, 2, 1, 0, 9], 8) 
test([0, 5, 1, 2, 3, 4, 6, 7, 8, 9], 5) 
test([4, 3, 0, 2, 1, 9, 8, 7, 6, 5], 0) 
test([2, 4, 5, 6, 7, 8, 9, 0, 1, 3], 2) # [FAIL: result = 3] 

def test(list, expected) 
    result = misplaced_number(list) 
    assert result == expected_value, "Got #{result} but expected #{expected} from list #{list}" 
end

來源

2013-05-20 10:01:14 Anurag

因此，結合srikanta和n.m.的哈斯克爾：

import Data.List (findIndex) 

f s = maybe (-1) (+1) . findIndex (==1) 
    $ zipWith (\a b -> abs (a - b)) s (drop 2 s ++ take 2 s) 


*Main> f [2,3,0,4,5,6,7,8,9,1] 
2 
*Main> f [5,6,7,9,8,0,1,2,3,4] 
3 
...

來源

2013-05-22 16:15:42

#include <stdio.h> 

int main(void) 
{ 
int array[10] = { 4, 3, 1, 0, 9, 8, 7, 2, 6, 5}; 

size_t idx; 
int diff, state,this,next; 

#define COUNT (sizeof array/sizeof array[0]) 
#define FOLD(n,i) ((i)%(n)) 
#define FETCH(a,i) a[FOLD(COUNT,(i))] 

this = FETCH(array,COUNT-1); 
next = FETCH(array,0); 
diff = next - this; 
state = (diff < -1 || diff >1) ? 1: 0; 
for (idx = 0; idx < COUNT; idx++) { 
     this = next; 
     next = FETCH(array,idx+1); 
     diff = next - this; 
     state = (state<<1) & 3; 
     state |= (diff < -1 || diff >1) ? 1: 0; 
     if (state==3) putc('*', stdout); 
     printf("%d ", this); 
     } 
putc('\n', stdout); 
return 0; 
}

輸出：

4 3 1 0 9 8 7 *2 6 5

來源

2013-05-23 00:02:09 wildplasser

int element, backdiff, forwarddiff; 
boolean elementFound = false; 

if(abs(a[0] - a[1]) == 2) 
    return "Out of Order Element is @ position" + (a[0] - a[1] > 0 ? 0 : 1); 
for (i=1;i<n;i++){ 
    if(!elementFound){ 
     backdiff = abs(a[i-1] - a[i]); 
     forwarddiff = abs(a[i+1] - a[i]); 
     if((backdiff == 1 && forwarddiff == 1) || 
      (backdiff == n-1 && forwarddiff == 1) || 
       (backdiff == 1 && forwarddiff == n-1)) 
      continue; 
     if(forwarddiff == 2 || backdiff == 2) 
      element = abs(a[i]-(a[i-1]+a[i+1])); 
      elementFound = true; 

     if(forwarddiff > 2 || backdiff > 2) 
      return "Out of Order Element is @ position" + (forwarddiff > 2 ? (i+1) : i); 

    } else { 
     if(a[i] == element) 
      return "Out of Order Element is @ position" + (i); 
    } 
}

來源

2013-10-03 01:11:20 user2840755

請不要只是轉儲代碼;解釋你的解決方案。 –

在「無序」數組中找到數字的最佳方法？

回答

相關問題