相对排序算法

我会带着你远行 2023-03-05 09:49 2阅读 0赞

**Description:** This a coding problem came in the coding round of Amazon, Microsoft.

**描述：**这是亚马逊，微软的编码回合中的编码问题。

**Problem Statement:**

**问题陈述：**

Given two array **A** and **B**, sort **A** in such a way that the relative order among the elements will be the same as those in **B**. For the elements not present in **B**, append them at last in sorted order. It is also given that the number of elements in **B** is smaller than or equal to the number of elements in **A** and **B** has all distinct elements.

给定两个阵列**A**和**B，**排序**甲**以这样的方式，该元件之间的相对顺序将是相同的那些**B中** 。 对于**B中**不存在的元素，最后按排序顺序附加它们。 还假定**B中**的元素数小于或等于**A中**的元素数，并且**B**具有所有不同的元素。

**Solution**

**解**

**Algorithm:**

**算法：**

1.  To solve the above problem vector is used to implement the arrays.
    
    为了解决上述问题，使用向量来实现数组。
2.  Initialize three vectors.
    
    初始化三个向量。
3.      Vector<int> a: for array A
        Vector<int> b: for array B
        Vector<int> c: for output array (relatively sorted array)
4.  Take input for array A and B
    
    接受数组A和B的输入
5.  Sort vector a using in-build sorting function.
    
    使用内置排序功能对向量a进行排序。
6.  For sorting the elements of a according to order of b,
    
    为了按照b的顺序对a的元素进行排序，
7.      For i=0:n2-1      //n2 be the no of elements of B&n1 of A
            For  j=0:n1-1 && a[j]<=b[i]    //maintaining the order of b
                if(a[j]==b[i])
                    inserta[j] into c;
                    Set a[j] to 0 for avoiding duplication
                End if
            End For loop
        End For loop
8.  The elements of vector a, also presented in vector b are sorted according to relative order of vector b. The rest of vector a is to be appended at the end of vector c in sorted way.
    
    向量a的元素， 矢量b还提出根据矢量b的相对排序。 向量a的其余部分将以排序方式附加在向量c的末尾。
9.  Just appended the rest of elements of vector a in vector c. (elements those are not zero).
    
    只需在向量c中追加向量a的其余元素。 (元素不为零)。
10. vector c is the desired output.
    
    向量c是所需的输出。

## C ++程序实现相对排序算法 **(**C++ program to implement relative sorting algorithm**)** ##

#include <bits/stdc++.h>
    using namespace std;
    
    vector<int> sorted(vector<int> a,vector<int> b,int n1,int n2){
        
    	vector <int> c;
    	// array a is sorted using labrary sorting function
    	sort(a.begin(),a.end()); 
    
    	for(int i=0;i<n2;i++){
        
    		for(int j=0;j<n1 && a[j]<=b[i];j++){
        
    			// elements of sorted a is entered to array c 
    			// maintaing the element order as in b
    			if(a[j]==b[i]){
        
    				c.push_back(a[j]);
    				//clear the element pushed into c
    				a[j]=0;
    			}
    		}
    	}
    
    	// the elements that are not in b is in being entered to c 
    	// in sorted manner as a is already sorted
    	for(int i=0;i<n1;i++)  
    		if(a[i]!=0)    //remaining elements of a
    			c.push_back(a[i]);
    			
    	//return the output
    	return c; 
    }
    
    
    int main() {
        
    	int n1,n2,u;
    	vector<int> :: iterator p; //iterator p
    
    	scanf("%d %d",&n1,&n2);
    
    	vector<int> a; //array a
    	vector<int> b;//array b
    
    	for(int j=0;j<n1;j++){
        
    		scanf("%d",&u);
    		// inputing elements of array a
    		a.push_back(u); 
    	}
    	for(int j=0;j<n2;j++){
        
    		scanf("%d",&u);
    		// inputing elements of array b
    		b.push_back(u);  
    	}
    
    	// implemented relative sorting function
    	vector<int> c=sorted(a,b,n1,n2); 
    	for(p=c.begin();p!=c.end();p++)	
    		printf("%d ",*p);  // printing the sorted array
    	printf("\n");
    
    	return 0;
    }

**Output**

**输出量**

enter length of array A & B respectively 
    10 
    5
    enter elements of array A
    2 5 12 2 8 9 13 5 8 12 
    enter elements of array B
    5 2 8 12 9 
    printing the relatively sorted array 
    5 5 2 2 8 8 12 12 9 13

> 翻译自: [https://www.includehelp.com/icp/relative-sorting.aspx][https_www.includehelp.com_icp_relative-sorting.aspx]

[https_www.includehelp.com_icp_relative-sorting.aspx]: https://www.includehelp.com/icp/relative-sorting.aspx