排序的搜索提高性能

-2

通過對testdome練習跑步......目前正在研究https://www.testdome.com/for-developers/solve-question/9877 排序的搜索提高性能

實現功能CountNumbers接受整數數組排序，並計算小於參數lessThan數組元素的數量。

例如，SortedSearch.CountNumbers(new int[] { 1, 3, 5, 7 }, 4)應該返回2，因爲還有不到4

我已經輸入了兩個數組元素：

public class SortedSearch 
{ 
    public static int CountNumbers(int[] sortedArray, int lessThan) 
    { 
     int returnedValued = 0; 

      foreach (int i in sortedArray) 
      { 
       if(i<lessThan) 
       returnedValued += 1; 
      } 

      return returnedValued; 
    } 

    public static void Main(string[] args) 
    { 
     Console.WriteLine(SortedSearch.CountNumbers(new int[] { 1, 3, 5, 7 }, 4)); 
    } 
}

我在想，爲什麼這個被標記爲難度硬預計時間20分鐘，當我知道它應該只需要幾個。無論如何，4例中有2例通過。我超出了時間限制，我猜我需要重構才能返回更快的搜索。這是正確的嗎？如果有的話，任何人都可以幫忙嗎？

  Example case: Correct answer 
     Various small arrays: Correct answer 
     Performance test when sortedArray contains lessThan: Time limit exceeded 
     Performance test when sortedArray doesn't contain lessThan: Time limit exceeded

來源

2017-09-23 John

如果你想知道爲什麼你的代碼不能通過測試，你需要詢問創建測試的人，而不是Stack Overflow社區。一個很好的問題會包含一些具體的可操作信息，比如確切的預期行爲和對目前爲止已經嘗試實現該行爲的具體解釋，以及您無法自行解決的具體問題。這個問題缺乏這些細節，並可能引發各種不同的答案。它太寬泛，不包含明確的問題陳述。 –

添加'使用System.Linq;'然後實現你的函數作爲'sortedArray.Where（i => i

另外，我只是看着網站，它確實有提示。你讀過任何提示嗎？如果不是，那麼在問這裏之前爲什麼不這樣做呢？如果是這樣，你讀了什麼提示，爲什麼他們不幫你解決問題？ **提示：第二個提示告訴你_exactly_你需要做什麼才能通過測試。** –

你應該打破的foreach循環，一旦如果條件得到錯誤的，因爲我們已經知道給數組進行排序，所以沒有點繼續評估其他元素。請參閱下面的代碼片段以供參考。

foreach (int i in sortedArray) 
{ 
    if (i < lessThan) 
     returnedValued += 1; 
    else break; 
}

請參閱下面通過所有4個測試的解決方案。我已經使用二分查找技術來找出大於的元素，而不是變量。

public static int CountNumbers(int[] sortedArray, int lessThan) 
{ 
    //Handle all the corner cases 
    int legthOfArray = sortedArray.Length; 
    if (legthOfArray == 0) return 0; 
    if (sortedArray[0] >= lessThan) return 0; 
    if (sortedArray[legthOfArray - 1] < lessThan) return legthOfArray; 
    return FindIndexGreaterOrEqualIndex(sortedArray, legthOfArray, lessThan, legthOfArray/2); 
} 

public static int FindIndexGreaterOrEqualIndex(int[] sortedArray, int lengthOfArray, int lessThan, int currentIndex) 
{ 
    while (true) 
    { 
     bool isCurrentElementLessThan = sortedArray[currentIndex] < lessThan; 
     if (isCurrentElementLessThan) // Traverse Right hand side of binary tree. 
      currentIndex = (int)Math.Ceiling((decimal)(currentIndex + lengthOfArray - 1)/2); 
     else if (sortedArray[currentIndex - 1] < lessThan && !isCurrentElementLessThan) //If array element is not less than and previous element is less than the given element. i.e. our answer so break the loop. 
      break; 
     else // Traverse Left hand side of binary tree. 
      currentIndex = (int)Math.Ceiling((decimal)currentIndex/2); 
    } 
    return currentIndex; 
}

看一看:)

來源

2017-09-23 08:52:10 Mukesh

該代碼將永久運行，用於以下輸入： Console.WriteLine（CountNumbers（new [] {1,2,3,4,5,6,7,8,9,10），5））; – Robie

他們希望你能使用Array.BinarySearch方法獲取100％。

using System; 

public class SortedSearch 
{ 
    public static int CountNumbers(int[] sortedArray, int lessThan) 
    { 
     if (sortedArray[0] >= lessThan) return 0; 

     int lengthOfArray = sortedArray.Length; 
     if (lengthOfArray == 0) return 0; 
     if (sortedArray[lengthOfArray - 1] < lessThan) return lengthOfArray; 

     int index = Array.BinarySearch(sortedArray, lessThan); 
     if (index < 0) 
      return ~index; 

     return index; 
    } 

    public static void Main(string[] args) 
    { 
     Console.WriteLine(SortedSearch.CountNumbers(new int[] { 1, 3, 5, 7 }, 4)); 
    } 
}

來源

2018-03-01 16:15:40

排序的搜索提高性能

回答

相關問題