給定無序的 n 個元素（1 到 n）的 2 個排列，我需要檢查是否可以使用以下交換方法從第一個元素轉到第二個元素：
選擇 3 個元素的子序列，我們稱它們為 (a,b,c)
你可以像這樣交換它們：(a,b,c)=> (c,a,b)。您可以無限次使用此方法
例如：對于輸入{1,3,4,2} {4,3,2,1}，它是可能的
但這不是為了 {1,2,3,4,5,6} {6,5,4,3,2,1}
我的第一種方法是從第一個排列中取出第一個元素，在第二個排列中找到它，然后模擬交換直到第一個元素相同，然后對每個元素執行以下操作，直到只剩下 3 個元素。那么很容易看出是否有可能從第一個到達第二個。
但是時間復雜度是O(n^2)，我必須做到O(n*log(n))或更少。
有什么辦法嗎？
uj5u.com熱心網友回復：
讓我們稱這種情況a[i] > a[j]為i < j錯位。請注意，如果元素是唯一的，則由交換引起的錯位數量的變化(a, b, c) -> (c, a, b)是偶數。因此，這種排列成為可能的必要條件是錯位（換位距離）數量的差異必須是偶數。
例子：
{1,2,3,4,5,6}: 0 錯位, {6,5,4,3,2,1}: 15 錯位。15 的差是奇數，因此這種排列是不可能的。
{1,3,4,2}：2 個錯位（3 個在 2 之前，4 個在 2 之前）
{4,3,2,1}：6 個錯位。4個錯位的差異是均勻的。
缺少什么：我有點懶得正式證明這是一個充分條件，即所有的變化都是可能的。此外，這不適用于具有非唯一元素的集合 - 我猜這些可能有任何排列。
要計算錯位的數量，請檢查Kendall tau 距離演算法。它需要一些適應，但會以~O（n log n）計算距離。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/415934.html
標籤：
上一篇：在c中找到一列二維陣列的最大和
下一篇：旋轉正數和負數的基于零的范圍