• 【离散化】【 树状树状 】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;
	}
};


    • 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
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99

    使用封装的离散类

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

    • 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

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

    • 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
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    扩展阅读

    视频课程

    有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。

  • 相关阅读:
    Leetcode—2216.美化数组的最少删除数【中等】
    Plink常见命令 --bfile --freq--recode --make-bed
    天软特色因子看板 (2023.08 第08期)
    SpringBoot
    etcd和redis的对比
    国产32位单片机有哪些
    2022 9.13 模拟
    HiveSQL在使用聚合类函数的时候性能分析和优化详解
    天脉操作系统（ACoreOS）
    我在2024年的第一个月
  • 原文地址：https://blog.csdn.net/he_zhidan/article/details/136428734