【算法】使数组有序的最小交换次数

int getMinSwap(vector &nums)
{
    mapmp;    
    vectorsort_nums(nums);
    sort(sort_nums.begin(),sort_nums.end());
    for (int i = 0; i 

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16

• 注意上述代码中，第二个for循环使用的是while，使用if会跳过某些元素。如下图对比。

• 使用if

• 使用while

• 相关题目
  • 6235. 逐层排序二叉树所需的最少操作数目
• 先层序遍历获取每层元素，然后对每层元素求有序最小的操作数目。

int minimumOperations(TreeNode* root) {
        int depth = 0;
        vector>layerContent;
        queueque;
        if(root)que.push(root);
        while(!que.empty()){
            int size = que.size();
            depth++;
            vectortmp;
            for(int i =  0; i < size;i++){
                TreeNode* node = que.front();
                que.pop();
                tmp.push_back(node->val);
                if(node->left)que.push(node->left);
                if(node->right)que.push(node->right);
            }
            layerContent.push_back(tmp);
        }
        // 已经获取二叉树的每层元素&层数
        int count = 0;
        for(int i = 1; i < depth;i++){
            count += getMinSwap(layerContent[i]);
        }
        return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25