用于计算置换中的有效块的数量的算法

Question

可能重复:
在排列中查找已排序的子序列

给定一个数组A,其中包含1,2,...,n的排列.如果A [i..j]
中出现的所有数字
都是连续数字(可能不是有序),则数组A的子块A [i..j] 被称为有效块.

给定阵列A = [7 3 4 1 2 6 5 8],有效块为[3 4],[1,2],[6,5],
[3 4 1 2],[3 4 1 2 6 5 ],[7 3 4 1 2 6 5],[7 3 4 1 2 6 5 8]

所以上面排列的计数是7.

给出O(n log n)算法来计算有效块的数量.

Answer 1

我的建议

STEP = 2 // 检测数量

B [0,0,0,0,0,0,0,0]

B [1,1,0,0,0,0,0,0]

VALID(A,B) - 如果无效则移一

B [0,1,1,0,0,0,0,0]

VALID(A,B) - 如果有效，则移动一步

B [0,0,0,1,1,0,0,0]

有效（A、B）

B [0,0,0,0,0,1,1,0]

步骤 = 3

B [1,1,1,0,0,0,0,0] 不行

B [0,1,1,1,0,0,0,0] 好的

B [0,0,0,0,1,1,1,0] 不行

步骤 = 4

B [1,1,1,1,0,0,0,0] 不行

B [0,1,1,1,1,0,0,0] 好的

……

CON <- 0
STEP <- 2
i <- 0
j <- 0
WHILE(STEP <= LEN(A)) DO
 j <- STEP
 WHILE(STEP <= LEN(A) - j) DO
  IF(VALID(A,i,j)) DO
   CON <- CON + 1
   i <- j + 1
   j <- j + STEP
  ELSE
   i <- i + 1
   j <- j + 1
  END
 END
 STEP <- STEP + 1
END

valid 方法检查所有元素是否连续

从未测试过，但可能没问题