查找對，使產品等於小於o（n^2）的第三個aaray的元素

-1

給定三個排序後的數組，如A，B和C.A和B的值範圍爲< 10^5，而對於C，範圍高達10^10，但所有C元素都是完美的正方形。計算A和B的所有對，以便產品等於C的任何元素。我嘗試過，但複雜度爲o（ N^2），我不能減少它，任何關於如何進行的建議？例如：A：[1,3,9,14] B：[4,12,49] C：[36,49,121] 答案：3 1來自A和49來自B 類似地3 * 12和4 * 9查找對，使產品等於小於o（n^2）的第三個aaray的元素

來源

2017-05-18 Coder doit

爲什麼你擔心O（n^2）？你有10^10個C元素，所以你的環境可以處理它。由於A和B本身不超過10^5，所以A和B的對也都是10^10。所以它看起來並不比計算C值本身更困難。 – Andrei

數組A，B和C可以有10^5個元素，所以o（n^2）在1秒內不會運行。 –

@Andrei我認爲這是元素的值達到10^5和10^10，不是元素的數量。至少在樣本輸入中元素的數量是4,3和3.擔心O（n^2）的原因很簡單，問題要求速度更快。你能否在這個基礎上闡述你的陳述？ – Yunnosch

句子"Find all the pairs A and B"是一個很好的指標，它不可能根據O(n^2)去。例如，讓我們挑選： A = [2 2 2], B[2 2 2], C = [4 4 4]，很容易看出我們有n^2對總計爲4.

來源

2017-05-18 19:14:47 NiVeR

問題糾正！ –

你改變了什麼？我認爲答案中所說的內容仍然有效。 – NiVeR

也許序列*嚴格*增加/減少？ – NiVeR

查找對，使產品等於小於o（n^2）的第三個aaray的元素

回答

相關問題