find-the-minimum-cost-array-permutation

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an array <code>nums</code> which is a permutation of <code>[0, 1, 2, ..., n - 1]</code>. The score of any permutation of <code>[0, 1, 2, ..., n - 1]</code> named <code>perm</code> is defined as:

<code>score(perm) = |perm[0] - nums[perm[1]]| + |perm[1] - nums[perm[2]]| + ... + |perm[n - 1] - nums[perm[0]]|</code>

Return the permutation <code>perm</code> which has the minimum possible score. If multiple permutations exist with this score, return the one that is lexicographically smallest among them.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [1,0,2]

Output: [0,1,2]

Explanation:

<img alt="" src="https://assets.leetcode.com/uploads/2024/04/04/example0gif.gif" style="width: 235px; height: 235px;" />

The lexicographically smallest permutation with minimum cost is <code>[0,1,2]</code>. The cost of this permutation is <code>|0 - 0| + |1 - 2| + |2 - 1| = 2</code>.
</div>

Example 2:

<div class="example-block">
Input: nums = [0,2,1]

Output: [0,2,1]

Explanation:

<img alt="" src="https://assets.leetcode.com/uploads/2024/04/04/example1gif.gif" style="width: 235px; height: 235px;" />

The lexicographically smallest permutation with minimum cost is <code>[0,2,1]</code>. The cost of this permutation is <code>|0 - 1| + |2 - 2| + |1 - 0| = 2</code>.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= n == nums.length &lt;= 14</code></li>
	<li><code>nums</code> is a permutation of <code>[0, 1, 2, ..., n - 1]</code>.</li>
</ul>

findPermutation

Find the Minimum Cost Array Permutation

Shortest Path Visiting All Nodes

shortest-path-visiting-all-nodes

访问所有节点的最短路径

Find the Shortest Superstring

find-the-shortest-superstring

最短超级串

Bit Manipulation

Array

Dynamic Programming

Bitmask

给你一个数组 <code>nums</code> ，它是 <code>[0, 1, 2, ..., n - 1]</code> 的一个排列 。对于任意一个 <code>[0, 1, 2, ..., n - 1]</code> 的排列 <code>perm</code> ，其 分数 定义为：

<code>score(perm) = |perm[0] - nums[perm[1]]| + |perm[1] - nums[perm[2]]| + ... + |perm[n - 1] - nums[perm[0]]|</code>

返回具有 最低 分数的排列 <code>perm</code> 。如果存在多个满足题意且分数相等的排列，则返回其中字典序最小的一个。

&nbsp;

示例 1：

<div class="example-block">
输入：nums = [1,0,2]

输出：[0,1,2]

解释：

<img alt="" src="https://assets.leetcode.com/uploads/2024/04/04/example0gif.gif" style="width: 235px; height: 235px;" />

字典序最小且分数最低的排列是 <code>[0,1,2]</code>。这个排列的分数是 <code>|0 - 0| + |1 - 2| + |2 - 1| = 2</code> 。
</div>

示例 2：

<div class="example-block">
输入：nums = [0,2,1]

输出：[0,2,1]

解释：

<img alt="" src="https://assets.leetcode.com/uploads/2024/04/04/example1gif.gif" style="width: 235px; height: 235px;" />

字典序最小且分数最低的排列是 <code>[0,2,1]</code>。这个排列的分数是 <code>|0 - 1| + |2 - 2| + |1 - 0| = 2</code> 。
</div>

&nbsp;

提示：

<ul>
	<li><code>2 &lt;= n == nums.length &lt;= 14</code></li>
	<li><code>nums</code> 是 <code>[0, 1, 2, ..., n - 1]</code> 的一个排列。</li>
</ul>