相关参考:
- 数组排序 使得交换次数最少,该文章中代码出现了一处错误，看起来作者好像很长时间没有更新了，在此纠正下。
- 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;
}
