快捷導(dǎo)航

go語(yǔ)言題解LeetCode1122數(shù)組的相對(duì)排序

更新時(shí)間：2022年12月29日 08:39:30 作者：劉09k11

這篇文章主要為大家介紹了go語(yǔ)言題解LeetCode1122數(shù)組的相對(duì)排序，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目描述

給你兩個(gè)數(shù)組，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每個(gè)元素都出現(xiàn)在 arr1 中。

對(duì) arr1 中的元素進(jìn)行排序，使 arr1 中項(xiàng)的相對(duì)順序和 arr2 中的相對(duì)順序相同。未在 arr2 中出現(xiàn)過(guò)的元素需要按照升序放在 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 中的每個(gè)元素 arr2[i] 都出現(xiàn)在 arr1 中

思路分析

最簡(jiǎn)單的就是暴力法了

解題思路

利用雙循環(huán)將數(shù)組1的數(shù)字依次與數(shù)組二相比較，相同則與前面元素交換位置
數(shù)組1中剩余元素利用sort函數(shù)進(jìn)行排序即可

vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        int tmp = 0;
        for(int i = 0;i<arr2.size();++i)
           for(int j = 0;j<arr1.size();++j){
               if(arr1[j] == arr2[i]){
                     swap(arr1[j],arr1[tmp]);
                     ++tmp;
               }
           }
           sort(arr1.begin()+tmp,arr1.end());
           return arr1;
    }

還有就是計(jì)數(shù)排序

解題思路

與遞增遞減排序不同，本題是根據(jù)數(shù)組順序自定義排序，因此最適合計(jì)數(shù)排序來(lái)實(shí)現(xiàn)（桶排序）

因?yàn)轭}意說(shuō)明數(shù)組中元素在0~1000之間，因此定義一個(gè)容量為1000的桶

第一個(gè)循環(huán)對(duì)數(shù)組1中的元素進(jìn)行計(jì)數(shù)，結(jié)果保存在桶中

第二個(gè)循環(huán)通過(guò)數(shù)組2，將重合的元素從數(shù)組1的0位置開(kāi)始插入

第三個(gè)循環(huán)，搜索桶中剩余的數(shù)組1元素，并把它們插入到數(shù)組1的后面。

vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) 
{
	vector<int> count(1001);
	for (int i = 0; i<arr1.size(); i++)
	{
		count[arr1[i]]++;
	}
	int k = 0;
	for (int i = 0; i<arr2.size(); i++)
	{
		while (count[arr2[i]]>0)
		{
			arr1[k++] = arr2[i];
			count[arr2[i]]--;
		}
	}
	for (int i = 0; i < count.size(); i++)
	{
		while (count[i] >0)
		{
			arr1[k++] = i;
			count[i]--;
		}
	}
	return arr1;
}

以上就是go語(yǔ)言題解LeetCode1122數(shù)組的相對(duì)排序的詳細(xì)內(nèi)容，更多關(guān)于go語(yǔ)言數(shù)組相對(duì)排序的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: