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

• 相关参考:

  • 数组排序 使得交换次数最少 ,该文章中代码出现了一处错误，看起来作者好像很长时间没有更新了，在此纠正下。
  • TsReaper-6235. 逐层排序二叉树所需的最少操作数目，参考该题解的评论区的作者解答，进行纠正。

• 贪心思想，每一步使得对应元素放到它该放的位置。

  • 先将要排序的数组复制一份，然后将其排序，使用哈希表记录排序后的数组对应元素与其对应下标。
  • 遍历原数组与排序后的数组，如果对应下标不相等，则根据哈希表记录该元素的下标进行交换。

int getMinSwap(vector<int> &nums)
{
    map<int,int>mp;    
    vector<int>sort_nums(nums);
    sort(sort_nums.begin(),sort_nums.end());
    for (int i = 0; i <sort_nums.size(); i++)mp[sort_nums[i]] = i ;//记录下标索引

    int cnt = 0;
    for (int i = 0; i < nums.size();i++){
        while (nums[i] !=sort_nums[i]){
            swap(nums[i],nums[mp[nums[i]]]);// 将元素放到它该在的位置
            cnt++;
        }   
    }
    return cnt;
}

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

• 使用if

• 使用while

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

int minimumOperations(TreeNode* root) {
        int depth = 0;
        vector<vector<int>>layerContent;
        queue<TreeNode*>que;
        if(root)que.push(root);
        while(!que.empty()){
            int size = que.size();
            depth++;
            vector<int>tmp;
            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;
}