這個題題意表達得可能沒那么清楚,如果說要求只能開O(N)的數(shù)組,時間復(fù)雜度也是O(N),那就是一個比較有趣的題。
我們可以用三次反轉(zhuǎn)的方法來思考這個題。
如果說我要把xy這個字符串的y字串移到x子串的左邊,變成yx,我記x^T為將x反轉(zhuǎn),如果x=”abc”,那么x^T=”cba”。
這樣,這里就有一個比較有意思的式子了
yx=(x^T y^T)^T
也就是說我們只需要進行三次反轉(zhuǎn),就可以實現(xiàn)我的操作。時間復(fù)雜度為6N,即O(N)
新聞熱點
疑難解答