優化這個C＃算法（K差異）

這是我解決（這是一個樣的問題，而不是一個真正的問題）問題：優化這個C＃算法（K差異）

給定N號，[N < = 10^5]我們需要計數的總對具有K. [K> 0和K < 1E9]

輸入格式的差數字：第一線包含N個& K（整數）。第二行包含N 這組數字。所有的N號碼都是有保證的。輸出格式：一個整數話說，沒有數字的對，有一個diff K.

Sample Input #00: 
5 2 
1 5 3 4 2 
Sample Output #00: 
3 
Sample Input #01: 
10 1 
363374326 364147530 61825163 1073065718 1281246024 1399469912 428047635 491595254 879792181 1069262793 
Sample Output #01: 
0

我已經有一個解決方案（和我有我一直沒能優化它，以及希望）。目前，我的解決方案在運行時獲得了12/15的分數，我想知道爲什麼我無法獲得15/15（我對另一個問題的解決方案效率並不高，但得到了所有要點）。顯然，代碼使用「Mono 2.10.1，C＃4」運行。

因此，任何人都可以想出更好的方法來進一步優化它嗎？ VS分析器說避免調用String.Split和Int32.Parse。 Int32.Parse的調用無法避免，但我想我可以優化標記數組。

我目前的解決方案：

using System; 
using System.Collections.Generic; 
using System.Text; 
using System.Linq; 

namespace KDifference 
{ 
    class Solution 
    { 
     static void Main(string[] args) 
     { 
     char[] space = { ' ' }; 

     string[] NK = Console.ReadLine().Split(space); 
     int N = Int32.Parse(NK[0]), K = Int32.Parse(NK[1]); 

     int[] nums = Console.ReadLine().Split(space, N).Select(x => Int32.Parse(x)).OrderBy(x => x).ToArray(); 

     int KHits = 0; 

     for (int i = nums.Length - 1, j, k; i >= 1; i--) 
     { 
      for (j = 0; j < i; j++) 
      { 
       k = nums[i] - nums[j]; 

       if (k == K) 
       { 
        KHits++; 
       } 
       else if (k < K) 
       { 
        break; 
       } 
      } 
     } 

     Console.Write(KHits); 
     } 
    } 
}

來源

2011-10-08 Neal P

我們不能看到PHP的解決方案問題沒有註冊。你能發佈你得分的標準嗎？ –

對，對不起。我認爲這對每個人都是開放的。具體的評分標準不會公佈，但代碼需要經過一系列測試。 –

您是否因減慢速度而減分？還是因爲錯了？或兩者？ –

你的算法仍然爲O（n^2），甚至與排序與早期輸出。即使你消除了O（n^2）位，排序仍然是O（n lg n）。 您可以使用O（n）算法來解決此問題。下面是做這件事：

假設你有一組是S1 = { 1, 7, 4, 6, 3 }不同的是2

構建集S2 = { 1 + 2, 7 + 2, 4 + 2, 6 + 2, 3 + 2 } = { 3, 9, 6, 8, 5 }。

您尋求的答案是S1和S2的交集的基數。該路口是{6, 3}，它有兩個元素，所以答案是2

您可以實現在一個單一的代碼行這一解決方案，前提是你有一個整數sequence的順序，以及整數difference：

int result = sequence.Intersect(from item in sequence select item + difference).Count();

Intersect方法將爲您創建一個高效的散列表，即O（n）來確定交集。

來源

2011-10-08 15:16:11

哦，謝謝。我應該想到這樣的事情。 –

這個算法真的很讓人印象深刻。你能否提供一些關於這種算法的資源？ – sahid

@Eric Lippert：是否有可能找到沒有o（n^2）複雜性的兩個數組的交集？ – Chetna

試試這個（注意，未經測試）：

排序數組在0
開始兩個指標如果在這些數字之間的差異兩個位置等於K，增加計數，並增加兩個指數中的一個（如果數字不重複，則同時增加）
如果差值大於K，增加索引＃1
如果差小於K，增加索引＃2，如果將其放置在陣列外，大功告成
否則，回到3繼續前進

基本上，儘量保持兩個指標相差K值的差異。

你應該爲你的算法寫出一系列的單元測試，並嘗試提出邊緣情況。

來源

2011-10-08 09:24:35

「所有的N號碼都是明確的。」 – CodesInChaos

O（n log n）而不是同樣簡單的O（n）解決方案。 – Voo

這可以讓你一次完成。如果有許多值要解析/檢查，使用散列集是有益的。您可能還希望將bloom filter與散列集結合使用以減少查找。

初始化。讓A和B是兩個空的哈希集合。讓c爲零。
解析循環。解析下一個值v。如果沒有更多值，則算法完成，結果在c。
返回檢查。如果v存在一個然後增加Ç和跳回2.
低配。如果N - K> 0然後：
- 插入N - ķ成甲
- 如果N - ķ存在於乙然後遞增Ç（以及可選地去除v - K from B）。
高的比賽。如果V +ķ< 1E9然後：
- 插入V +ķ成甲
- 如果存在於乙V +ķ然後遞增Ç（以及可選地去除v + K from B）。
記住。插入v到乙。
跳回2.

來源

2011-10-08 10:15:42

其實這是平凡的一個HashMap來解決：

首先把每個數字到一個HashMap：dict((x, x) for x in numbers)在「pythony」僞代碼;）

現在，您只需遍歷散列映射中的每個數字，並檢查數字+ K是否在散列映射中。如果是的話，增加一個。

明顯改善天真的解決辦法是隻檢查了更高（或更低）的約束，否則你得到的結果雙，並有2之後分 - 沒用。

這是O（N）創建hashmap時，當讀取的值和O（N）時迭代通過，即O（N）和約8loc在Python中（這是正確的，我剛解決它; - ））

來源

2011-10-08 14:49:05 Voo

繼Eric的回答，粘貼下面Interscet方法的實現，它是O（n）：

private static IEnumerable<TSource> IntersectIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer) 
{ 
    Set<TSource> set = new Set<TSource>(comparer); 
    foreach (TSource current in second) 
    { 
     set.Add(current); 
    } 
    foreach (TSource current2 in first) 
    { 
     if (set.Remove(current2)) 
     { 
      yield return current2; 
     } 
    } 
    yield break; 
}

來源

2013-01-31 15:43:53 rockXrock

//這個K特色

function getEqualSumSubstring($l,$s) { 
$s = str_replace(' ','',$s); 
$l = str_replace(' ','',$l); 

for($i=0;$i<strlen($s);$i++) 
{ 
    $array1[] = $s[$i]; 
} 
for($i=0;$i<strlen($s);$i++) 
{ 
    $array2[] = $s[$i] + $l[1]; 
} 
return count(array_intersect($array1,$array2)); 

} 

echo getEqualSumSubstring("5 2","1 3 5 4 2");

來源

2013-04-25 18:28:11

優化這個C＃算法（K差異）

回答

相關問題