开发者

go语言题解LeetCode1122数组的相对排序

开发者 https://www.devze.com 2022-12-29 11:11 出处:网络 作者: 刘09k11
目录题目描述 1122. 数组的相对排序 - 力扣(LeetCode) 给你两个数组,arr1 和 arr2,arr2 中的元素各不相同,arr2 中的每个元素都出现在 arr1python 中。
目录

    题目描述

    1122. 数组的相对排序 - 力扣(LeetCode)

    给你两个数组,arr1 和 arr2arr2 中的元素各不相同,arr2 中的每个元素都出现在 arr1python 中。

    arr1 中的元素进行排序,使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

    示例 1:

    输入:arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
    输出:[2,2,2,1,4,3,3,9,6,7,19]
    复制代码

    示例  2:

    输入:arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
    输出:[22,28,8,6,17,44]
    复制代码

    提示:

    • 1 <= arr1.length, arr2.length <= 1000
    • 0 <= arr1[i], arr2[i] <= 1000
    • arr2 中的元素 arr2[i]  各不相同 
    • arr2 中的每个元素 arr2[i] 都出现在 arr1 中

    思路分析

    最简单的就是 暴力法 了

    解题思路

    利用双循环将数组1的数字依次与数组二相比较,相同则与前面元素交换位置

    数组1中剩余元素利用sort函数进行排序即可

    vector&lt;int&gt; relativeSortArray(vector&lt;int&gt;&amp; arr1, vector&lt;int&gt;&amp; arr2) {
            int tmp = 0;
            for(int i = 0;i&lt;arr2.size();++i)
               for(int j = 0;j&lt;arr1.size();++j){
                   if(arr1[j] == arr2[i]){
                         swap(arr1[j],arr1[tmp]);
                         ++tmp;
                   }
               }
               sort(arr1.begin()+tmp,arr1.end());
               retuhttp://www.devze.comrn arr1;
        }
    复制代码

    还有就是 计数排序

    解题思路

    与递增递减排序不同,本题是根据数组顺序自定义排序,因此最适合计数排序来实现(桶排序)

    因为题意说明数组中元素在0~1000之间,因此定义一个容量为1000的桶

    第一个循环对数组1中的元素进行计数,结果保存在桶中

    第二个循环通过数组2,将重合的元素从数组1的0位置开始插入

    第三个循环,搜索桶中剩余的数组1元素,并把它们插入到数组1的后面。

    vector&lt;int&开发者_JS教程;gt; relativeSortArray(vector&lt;int&gt;&amp; arr1, vector&lt;int&gt;&amp; arr2) 
    {
    	vector&lt;int&gt; count(1001);
    	for (int i = 0; i&lt;arr1.size(); i++)
    	{
    		count[arr1[i]]++;
    	}
    	int k = 0;
    	for (int i = 0; i&lt;arr2.size(); i++)
    	{
    		while (count[arr2[i]]&gt;0)
    		{
    			arr1[k++] = arr2[i];
    			count[arr2[i]]--;
    		}
    	}
    	for (i编程nt i = 0; i &lt; count.si编程客栈ze(); i++)
    	{
    		while (count[i] &gt;0)
    		{
    			arr1[k++] = i;
    			count[i]--;
    		}
    	}
    	return arr1;
    }

    以上就是go语言题解LeetCode1122数组的相对排序的详细内容,更多关于androidgo语言数组相对排序的资料请关注我们其它相关文章!

    0

    精彩评论

    暂无评论...
    验证码 换一张
    取 消

    关注公众号