從給定的算術級數中找出缺失的數字

Question

我遇到了這個問題，在那裏給出了一個N作爲輸入，然後輸入了N個數字（其中3 < = N < = N）。這些N數字是算術級數（大小爲N+1）的一部分，從中刪除了一個數字。所以任務是找到那個失蹤號碼。例如

5 
1 3 5 9 11 

輸出是7

我想出了兩種方法，第2個路過一個所有的測試用例，但第一個在特定的（隱藏）的情況下失敗。

首先，我將解釋第二種方法

方法II

Let diff=(last_number-first_number)/N 
//Considering 0 based indexing 
for i=0 to (N-2) 
    if(array[i+1] is not equal to (array[i]+diff)) 
      print (array[i]+diff) 
      break 

這種方法通過了所有的測試案例。現在我實現和第一種方法失敗一定的測試用例是如下

方法我

//Considering 0 based indexing 
for i=1 to (N-2) 
     if (2*array[i] is not equal to (array[i-1]+array[i+1])) then 
       if((array[i]-array[i-1])< (array[i+1]-array[i])) 
         print 2*array[i]-array[i-1] 
       else 
         print 2*array[i]-array[i+1] 
       break 

誰能解釋一下什麼是錯METHOD I？我錯過了哪些案件。 謝謝。

Answer 1

當數字按降序排列時，方法1不起作用。

對於7 5 1輸出應該是3，但該算法將給9.

方法2個工作在這種情況下，因爲差作爲陰性正確地計算，並且該算法相應地繼續進行。

Answer 2

雖然沒有回答你原來的問題，但如果你需要它一個更好的解決方案與O（logN）的複雜性找到缺少的數字（如果只有一個）。使用二進制搜索。對於二進制搜索

if(a[mid] != mid*(difference)+a[0]) { 

     missing_num = mid*(difference) + a[0]; 
     search lower half 
    } 

    else search higher half 

Answer 3

Works的

1）將N的任何值

化妝以下對比（給定的例子中5）

2）項之間的任何差異（例如，在給定的2 ）

3）差值可以是+以及 - （例如：11 5 2 -1 -4）

int diff[]= new int[length-1]; 
for(int i = 0; i<length-1;i++){ 
    diff[i] = n1[i+1]-n1[i]; 
    System.out.println(diff[i]); 
    if(i!=0){ 
     if(diff[i]<diff[i-1]){ 
      if(diff[i]<0) 
       System.out.println(n1[i]+diff[i-1]); 
      else 
       System.out.println(n1[i-1]+diff[i]); 
      break; 
     } 
     if(diff[i]>diff[i-1]){ 
      if(diff[i]<0) 
       System.out.println(n1[i-1]+diff[i]); 
      else 
       System.out.println(n1[i]+diff[i-1]); 
      break; 
     } 
    } 
} 

n1是您存儲String中數字數組的地方。

長度是您提供多少個號碼。

這是優化的，這樣，如果你在第一次兩個數字之間錯過數則只循環3次，不管你有多少個號碼給

Answer 4

這是我在Ruby中的解決方案：

number_of_terms = gets.chomp.to_i 

獲取方面的數量從STDIN

progression = gets.chomp.split(' ').map(&:to_i) 

獲取字符串，刪除任何開頭和結尾的空白，在數字之間的空間分割，然後將每個項目我nto整數。

expected_sum = (number_of_terms+1)/2.0*(progression.first+progression.last) 

將公式用於算術級數的總和：n/2（a [0] + a [n]）。

這裏除以2.0是重要的。需要保持精確度。

actual_sum = progression.inject(:+) 

檢查給定數字的總和是多少。

missing_element = (expected_sum - actual_sum).to_i 

差異當然是缺少的元素。也轉換爲整數，以除去後0.0

即4.0 => 4

puts "Missing element is: #{missing_element}" 

Answer 5

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

int findDelta(long *x, int n); 

int main(){ 
    int n; 
     fscanf(stdin,"%d",&n); 
     long *x= (long*) calloc(n,sizeof(long)); 
    long k; 
    for(int i=0;i<n;i++){ 
     scanf("%ld",&k); 
     x[i]=k; 
    } 

    int delta=findDelta(x,n); 
    for(int i=0;i<n-1;i++){ 
     if (x[i+1]-x[i] != delta) 
      printf("%ld\n",x[i]+delta); 
    } 
    free(x);  
    return 0; 
} 

int findDelta(long *x, int n){ 
    long delta1,delta2; 
    delta1=x[1]-x[0]; 
    int d1Count=0; 
    int d2Count=0; 

    for(int i=1;i<n-1;i++){ 
     delta2=x[i+1]-x[i]; 
     if(delta2==delta1) 
      d1Count++; 
     else 
      d2Count++; 
    } 
    if (d1Count > d2Count) 
     return (delta1); 
    else 
     return (delta2); 
}