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

5
  • 相关参考:

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

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

在这里插入图片描述

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;
}