备案控制台
开发者社区 开发与运维 文章 正文

【离散化】【 树状树状 】100246 将元素分配到两个数组中

2024-04-10 16
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【离散化】【 树状树状 】100246 将元素分配到两个数组中

本文涉及知识点

离散化 树状树状

LeetCode 100246 将元素分配到两个数组中

给你一个下标从 1 开始、长度为 n 的整数数组 nums 。

现定义函数 greaterCount ，使得 greaterCount(arr, val) 返回数组 arr 中 严格大于 val 的元素数量。

你需要使用 n 次操作，将 nums 的所有元素分配到两个数组 arr1 和 arr2 中。在第一次操作中，将 nums[1] 追加到 arr1 。在第二次操作中，将 nums[2] 追加到 arr2 。之后，在第 i 次操作中：

如果 greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]) ，将 nums[i] 追加到 arr1 。

如果 greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i]) ，将 nums[i] 追加到 arr2 。

如果 greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i]) ，将 nums[i] 追加到元素数量较少的数组中。

如果仍然相等，那么将 nums[i] 追加到 arr1 。

连接数组 arr1 和 arr2 形成数组 result 。例如，如果 arr1 == [1,2,3] 且 arr2 == [4,5,6] ，那么 result = [1,2,3,4,5,6] 。

返回整数数组 result 。

示例 1：

输入：nums = [2,1,3,3]

输出：[2,3,1,3]

解释：在前两次操作后，arr1 = [2] ，arr2 = [1] 。

在第 3 次操作中，两个数组中大于 3 的元素数量都是零，并且长度相等，因此，将 nums[3] 追加到 arr1 。

在第 4 次操作中，两个数组中大于 3 的元素数量都是零，但 arr2 的长度较小，因此，将 nums[4] 追加到 arr2 。

在 4 次操作后，arr1 = [2,3] ，arr2 = [1,3] 。

因此，连接形成的数组 result 是 [2,3,1,3] 。

示例 2：

输入：nums = [5,14,3,1,2]

输出：[5,3,1,2,14]

解释：在前两次操作后，arr1 = [5] ，arr2 = [14] 。

在第 3 次操作中，两个数组中大于 3 的元素数量都是一，并且长度相等，因此，将 nums[3] 追加到 arr1 。

在第 4 次操作中，arr1 中大于 1 的元素数量大于 arr2 中的数量（2 > 1），因此，将 nums[4] 追加到 arr1 。

在第 5 次操作中，arr1 中大于 2 的元素数量大于 arr2 中的数量（2 > 1），因此，将 nums[5] 追加到 arr1 。

在 5 次操作后，arr1 = [5,3,1,2] ，arr2 = [14] 。

因此，连接形成的数组 result 是 [5,3,1,2,14] 。

示例 3：

输入：nums = [3,3,3,3]

输出：[3,3,3,3]

解释：在 4 次操作后，arr1 = [3,3] ，arr2 = [3,3] 。

因此，连接形成的数组 result 是 [3,3,3,3] 。

提示：

3 <= n <= 105

1 <= nums[i] <= 109

预备知识

本题的数据最大109，如果不离散化，空间复杂度会超。

离散化：不改变各数值相对大小的前提下，尽可能得减小各数值。

比如：{3,7,7,8} 变成{1,2,2,3}。

树状数组，可以在O(logn)时间更新数值和求和。

代码

template<class ELE = int >
class CTreeArr
{
public:
  CTreeArr(int iSize) :m_vData(iSize + 1)
  {
  }
  void Add(int index, ELE value)
  {
    index++;
    while (index < m_vData.size())
    {
      m_vData[index] += value;
      index += index & (-index);
    }
  }
  ELE Sum(int index)
  {
    index++;
    ELE ret = 0;
    while (index)
    {
      ret += m_vData[index];
      index -= index & (-index);
    }
    return ret;
  }
  ELE Get(int index)
  {
    return Sum(index) - Sum(index - 1);
  }
private:
  vector<ELE> m_vData;
};
class CTreeArrHlp
{
public:
  CTreeArrHlp(vector<int> nums)
  {
    sort(nums.begin(), nums.end());
    nums.erase(std::unique(nums.begin(), nums.end()), nums.end());
    for (int i = 0; i < nums.size(); i++)
    {
      mValueToIndex[nums[i]] = i;
    }
    m_pTreeArr = new CTreeArr<int>(nums.size());
  }
  void Add(const int& val)
  {
    m_nums.emplace_back(val);
    m_pTreeArr->Add(mValueToIndex[val], 1);
  }
  int MoreCnt(const int& val)
  {
    return m_nums.size() - m_pTreeArr->Sum(mValueToIndex[val]);
  }
  vector<int> m_nums;
protected:
  CTreeArr<int>* m_pTreeArr;
  unordered_map<int, int> mValueToIndex;
  
};
class Solution {
public:
  vector<int> resultArray(vector<int>& nums) {
    CTreeArrHlp hlp1(nums), hlp2(nums);
    hlp1.Add(nums[0]);
    hlp2.Add(nums[1]);    
    for (int i = 2; i < nums.size(); i++)
    {
      const int i1 = hlp1.MoreCnt(nums[i]);
      const int i2 = hlp2.MoreCnt(nums[i]);
      if (i1 > i2)
      {
        hlp1.Add(nums[i]);
      }
      else if (i1 < i2)
      {
        hlp2.Add(nums[i]);
      }
      else
      {
        if (hlp1.m_nums.size() <= hlp2.m_nums.size())
        {
          hlp1.Add(nums[i]);
        }
        else
        {
          hlp2.Add(nums[i]);
        }
      }
    }
    hlp1.m_nums.insert(hlp1.m_nums.end(), hlp2.m_nums.begin(), hlp2.m_nums.end());
    return hlp1.m_nums;
  }
};

使用封装的离散类

template
class CTreeArr
{
public:
CTreeArr(int iSize) :m_vData(iSize + 1)
{
}
void Add(int index, ELE value)
{
  index++;
  while (index < m_vData.size())
  {
    m_vData[index] += value;
    index += index & (-index);
  }
}
ELE Sum(int index)
{
  index++;
  ELE ret = 0;
  while (index)
  {
    ret += m_vData[index];
    index -= index & (-index);
  }
  return ret;
}
ELE Get(int index)
{
  return Sum(index) - Sum(index - 1);
}
private:
vector m_vData;
};
class CDiscretize //离散化
{
public:
CDiscretize(vector nums)
{
sort(nums.begin(), nums.end());
nums.erase(std::unique(nums.begin(), nums.end()), nums.end());
for (int i = 0; i < nums.size(); i++)
{
m_mValueToIndex[nums[i]] = i;
}
}
int operator[](const int value)const
{
auto it = m_mValueToIndex.find(value);
if (m_mValueToIndex.end() == it)
{
return -1;
}
return it->second;
}
int size()const
{
return m_mValueToIndex.size();
}
protected:
unordered_map<int, int> m_mValueToIndex;
};
class CTreeArrHlp
{
public:
CTreeArrHlp(vector nums):m_dis(nums),m_treeArr(m_dis.size())
{
}
void Add(const int& val)
{
m_nums.emplace_back(val);
m_treeArr.Add(m_dis[val], 1);
}
int MoreCnt(const int& val)
{
return m_nums.size() - m_treeArr.Sum(m_dis[val]);
}
vector m_nums;
protected:
CDiscretize m_dis;
CTreeArr m_treeArr;
};
class Solution {
public:
vector resultArray(vector& nums) {
CTreeArrHlp hlp1(nums), hlp2(nums);
hlp1.Add(nums[0]);
hlp2.Add(nums[1]);
for (int i = 2; i < nums.size(); i++)
{
const int i1 = hlp1.MoreCnt(nums[i]);
const int i2 = hlp2.MoreCnt(nums[i]);
if (i1 > i2)
{
hlp1.Add(nums[i]);
}
else if (i1 < i2)
{
hlp2.Add(nums[i]);
}
else
{
if (hlp1.m_nums.size() <= hlp2.m_nums.size())
{
hlp1.Add(nums[i]);
}
else
{
hlp2.Add(nums[i]);
}
}
}
hlp1.m_nums.insert(hlp1.m_nums.end(), hlp2.m_nums.begin(), hlp2.m_nums.end());
return hlp1.m_nums;
}
};

测试用例

template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  vector<int> nums = { 11,92,25,90 };
  {
    Solution sln;
    ;
    auto res = sln.resultArray(nums);
    Assert({ 11,92,25,90 }, res);
  }
  
}


扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。

文章标签：
算法
C++
测试技术
C#
闻缺陷则喜何志丹
目录
相关文章
泡沫o0
|
5天前
|
算法 C++ 开发者
【C/C++ 数据结构 】图顶点个数和边的关系
【C/C++ 数据结构 】图顶点个数和边的关系
泡沫o0
32 0
吉士先生
|
8月前
56.【树型结构】（三）
56.【树型结构】
吉士先生
39 0
盖丽男
|
5天前
|
JavaScript Java
树状结构数据按照顺序排序
树状结构数据按照顺序排序
盖丽男
14 0
秋之合
|
10月前
数组转树形结构的两种实现
数组转树形结构的两种实现
秋之合
29 0
吉士先生
|
8月前
|
机器学习/深度学习
56.【树型结构】（一）
56.【树型结构】
吉士先生
53 0
年少轻与狂
|
9月前
|
存储 C++
数据结构之 图（一） 图的存储结构
数据结构之 图（一） 图的存储结构
年少轻与狂
55 0
clichong
|
存储 算法
【数据结构和算法】图的各类概念与图的存储结构（还有十字链表与邻接多重表的介绍）
【数据结构和算法】图的各类概念与图的存储结构（还有十字链表与邻接多重表的介绍）
clichong
173 0
【数据结构和算法】图的各类概念与图的存储结构（还有十字链表与邻接多重表的介绍）
小蔡coding
|
机器学习/深度学习 数据库管理
大话数据结构--初始树
大话数据结构--初始树
小蔡coding
50 0
wb7zts3t7svdo
|
存储
树型结构——二叉数
树型结构——二叉数
wb7zts3t7svdo
95 0
树型结构——二叉数
柠檬叶子C
|
机器学习/深度学习 存储 搜索推荐
【数据结构】树的概念与结构 | 树的几种常见表示方法
本章将正式开启数据结构中 “树” 部分的讲解，本章将介绍树的概念和结构，以及树的表示方法。
柠檬叶子C
163 0
【数据结构】树的概念与结构 | 树的几种常见表示方法