題目連結
題意:
每行測資給定一個permutation (即 0, 1, . . . , n − 1元素的一種排列)，判斷其中是否包含任3個數形成等差數列，若否，稱為 antiarithmetic permutation，輸出yes；若存在，輸出no
例如:
4 5 0 3 1 2
其中的 4 3 2 是等差數列，所以要輸出 no
解法:
一開始我用暴力解，每次找到等差前、中項後
都會一一走訪到數列尾以找後項，果不其然TLE了
包含透過Arraylist 的 indexOf 方法
時間複雜度可能落在 O(N^3)...
(Worst case 前中後項)
後來只好爬文
看到網路上大多是在讀取數列的同時記錄位置
因為permutation就是該數列恰包含 0 ~ n-1 的元素
我們只要倒過來
用陣列的 index 表示真正的數值
陣列存的值則為原本數列的位置所在
以 4 5 0 3 1 2 為例
陣列第 4 格擺 0, 第 5 格擺 1, 第 0 格擺 2, 依此類推
從陣列裡，我們可以知道
數值 0 在原數列 2 的位置
數值 1 在原數列 4 的位置
...
而3元素的等差數列的定義為: 前項, 前項+公差, 前項+2*公差
也就是我們只要依次判斷
arr[0], arr[1], arr[2] (公差1)
arr[0], arr[2], arr[4] (公差2)
arr[1], arr[2], arr[3] (公差1)
arr[1], arr[3], arr[5] (公差2)
...
存的值是不是遞增(也就是在原本數列也是照順序出現)
或是遞減(公差為負的情況)
像這個例子，arr[0], arr[1], arr[2]遞增，所以輸出 no
大概評估一下，時間複雜度應該在O(N^2)以下
(前項N，公差從1枚舉到 後項到數列長度前)
程式(Java):
題意:
每行測資給定一個permutation (即 0, 1, . . . , n − 1元素的一種排列)，判斷其中是否包含任3個數形成等差數列，若否，稱為 antiarithmetic permutation，輸出yes；若存在，輸出no
例如:
4 5 0 3 1 2
其中的 4 3 2 是等差數列，所以要輸出 no
解法:
一開始我用暴力解，每次找到等差前、中項後
都會一一走訪到數列尾以找後項，果不其然TLE了
包含透過Arraylist 的 indexOf 方法
時間複雜度可能落在 O(N^3)...
(Worst case 前中後項)
後來只好爬文
看到網路上大多是在讀取數列的同時記錄位置
因為permutation就是該數列恰包含 0 ~ n-1 的元素
我們只要倒過來
用陣列的 index 表示真正的數值
陣列存的值則為原本數列的位置所在
以 4 5 0 3 1 2 為例
陣列第 4 格擺 0, 第 5 格擺 1, 第 0 格擺 2, 依此類推
從陣列裡，我們可以知道
數值 0 在原數列 2 的位置
數值 1 在原數列 4 的位置
...
而3元素的等差數列的定義為: 前項, 前項+公差, 前項+2*公差
也就是我們只要依次判斷
arr[0], arr[1], arr[2] (公差1)
arr[0], arr[2], arr[4] (公差2)
arr[1], arr[2], arr[3] (公差1)
arr[1], arr[3], arr[5] (公差2)
...
存的值是不是遞增(也就是在原本數列也是照順序出現)
或是遞減(公差為負的情況)
像這個例子，arr[0], arr[1], arr[2]遞增，所以輸出 no
大概評估一下，時間複雜度應該在O(N^2)以下
(前項N，公差從1枚舉到 後項到數列長度前)
程式(Java):
留言
張貼留言