leetcode.1122. 数组的相对排序(relative-sort-array)

「爱情、让人受尽委屈。」 2022-12-21 03:11 117阅读 0赞

# 1122. 数组的相对排序(relative-sort-array) #

给你两个数组，`arr1` 和 `arr2`，

`arr2` 中的元素各不相同  
`arr2` 中的每个元素都出现在 `arr1` 中  
对 `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 = [2,3,1,3,2,4,6,7,9,2,19], arr2=[4,3,9,6]
    输出：[4,3,3,9,6,1,2,2,2,7,19]

提示：

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

# 代码与思路 #

这道题目包含的信息很多，关键是看清楚示例的输出，`[2,2,2,1,4,3,3,9,6,7,19]`前面有三个连着的`2`，题目说了`arr2`的中元素是各不相同的，没有说`arr1`中的元素的特征，但是可以从输入的`arr1`和`输出`看出，`arr1`是有重复元素的。题目中还有一点，未在 `arr2` 中出现过的元素需要按照升序放在 `arr1` 的末尾，也就是说在新的数组中(返回的那个数组)，`arr2`的元素排在前面。

## 计数排序 ##

class Solution { 
        public int[] relativeSortArray(int[] arr1, int[] arr2) { 
            int[] nums = new int[1001];
            int[] res = new int[arr1.length];
            //遍历arr1,统计每个元素的数量
            for (int i : arr1) { 
                nums[i]++;
            }
            //遍历arr2,处理arr2中出现的元素
            int index = 0;
            for (int i : arr2) { 
                while (nums[i]>0){ 
                    res[index++] = i;
                    nums[i]--;
                }
            }
            //遍历nums,处理剩下arr2中未出现的元素
            for (int i = 0; i < nums.length; i++) { 
                while (nums[i]>0){ 
                    res[index++] = i;
                    nums[i]--;
                }
            }
            return res;
        }
    }

## 纯c实现 ##

/* 封装uthash开始 */
    struct HashTable { 
        int k;
        int v;
        UT_hash_handle hh;
    };
    
    typedef struct HashTable HashTable;
    typedef struct HashTable NodeHashTable;
    
    HashTable *newHashTable( void ) { 
        return NULL;
    }
    
    int putHashTable( HashTable **hashTable, int key, int val ) { 
        NodeHashTable *n = NULL;
    
        HASH_FIND_INT( *hashTable, &key, n );
        if( n == NULL ) { 
            n = (NodeHashTable *) malloc( sizeof(*n) );
            n->k = key;
            HASH_ADD_INT( *hashTable, k, n );
        }
        n->v = val;
    
        return val;
    }
    
    int removeHashTable( HashTable **hashTable, int key ) { 
        int v = 0;
        NodeHashTable *n = NULL;
    
        HASH_FIND_INT( *hashTable, &key, n );
        if( n != NULL ) { 
            v = n->v;
            HASH_DEL( *hashTable, n );
            free( n );
        }
    
        return v;
    }
    
    int getHashTable( HashTable *hashTable, int key ) { 
        NodeHashTable *n = NULL;
    
        HASH_FIND_INT( hashTable, &key, n );
    
        return n->v;
    }
    
    NodeHashTable *addressHashTable( HashTable *hashTable, int key ) { 
        NodeHashTable *n = NULL;
    
        HASH_FIND_INT( hashTable, &key, n );
    
        return n;
    }
    
    int existHashTable( HashTable *hashTable, int key ) { 
        NodeHashTable *n = NULL;
    
        HASH_FIND_INT( hashTable, &key, n );
    
        return n != NULL;
    }
    
    int sizeHashTable( HashTable *hashTable ) { 
        return HASH_COUNT( hashTable );
    }
    
    int emptyHashTable( HashTable *hashTable ) { 
        return !(HASH_COUNT( hashTable ));
    }
    
    void traverseHashTable( HashTable *hashTable ) { 
        NodeHashTable *n = NULL;
    
        for( n = hashTable; n != NULL; n = n->hh.next ) { 
            printf( "k = %d, v = %d\n", n->k, n->v );
        }
    }
    
    void cleanHashTable( HashTable *hashTable ) { 
        NodeHashTable *current = NULL, *temp = NULL;
    
        HASH_ITER( hh, hashTable, current, temp ) { 
            HASH_DEL( hashTable, current );
            free( current );
        }
    }
    
    void delHashTable( HashTable *hashTable ) { 
        cleanHashTable( hashTable );
    }
    /* 封装uthash结束 */
    
    
    
    /* 随机快排实现开始 */
    #if 0
    static void array_2elem_swap( int a[], int i, int j ) { 
        int temp = a[i];
    
        a[i] = a[j];
        a[j] = temp;
    }
    #else
    #define \ array_2elem_swap( a, i, j ) ({ \ int i1 = (i), j1 = (j); \ int temp = *((a) + i1); \ *((a) + i1) = *((a) + j1); \ *((a) + j1) = temp; \ })
    #endif
    
    static void array_partition( int a[], int left, int right, int boundary[2] ) { 
        int l = left - 1, c = left, r = right;
    
        // left + rand() % (right - left) 取值区间: [left, right).
        // left + rand() % (right - left + 1) 取值区间: [left, right].
        array_2elem_swap( a, left + rand() % (right - left), right );
        while( c < r ) { 
            if( a[c] < a[right] ) { 
                array_2elem_swap( a, c++, ++l );
            } else if( a[c] > a[right] ) { 
                array_2elem_swap( a, c, --r );
            } else { 
                ++c;
            }
        }
        array_2elem_swap( a, r, right );
        boundary[0] = l + 1;
        boundary[1] = r;
    }
    
    void array_sort_quick( int a[], int left, int right ) { 
        int boundary[2] = { -1,-1};
    
        srand( (unsigned int)time( NULL ) );
        if( left < 0 || left >= right ) { 
            return;
        }
        array_partition( a, left, right, boundary );
        array_sort_quick( a, left, boundary[0] - 1 );
        array_sort_quick( a, boundary[1] + 1, right );
    }
    /* 随机快排实现结束 */
    
    
    
    /** * Note: The returned array must be malloced, assume caller calls free(). */
    int *relativeSortArray(int *arr1, int arr1Size, int *arr2, int arr2Size, int *returnSize ) { 
        int *returnArray = NULL, *help = NULL;
        HashTable *hashTable = NULL;
        int i = 0, helpI = 0;
        int count = 0, j = 0;
    
        returnSize[0] = 0;
        if( arr1Size < 1 || arr2Size < 1 ) { 
            return NULL;
        }
        returnArray = (int *) malloc( sizeof(*returnArray) * arr1Size );
        help = (int *) malloc( sizeof(*help) * arr1Size );
    
        for( i = 0; i < arr2Size; ++i ) {  // 把arr2中的元素都加入到哈希表中, 值初始为0.
            putHashTable( &hashTable, arr2[i], 0 );
        }
    
        for( i = 0; i < arr1Size; ++i ) { 
            if( existHashTable( hashTable, arr1[i] ) ) {  // arr1[i] 存在arr2中, 利用哈希表统计个数.
                putHashTable( &hashTable, arr1[i], getHashTable( hashTable, arr1[i] ) + 1 );
            } else { 
                help[helpI++] = arr1[i];
            }
        }
    
        for( i = 0; i < arr2Size; ++i ) {  // 还原arr2顺序.
            count = getHashTable( hashTable, arr2[i] );
            for( j = 0; j < count; ++j ) { 
                returnArray[returnSize[0]++] = arr2[i];
            }
        }
    
        array_sort_quick( help, 0, helpI - 1 ); // 排序不存在arr2中的元素.
        for( i = 0; i < helpI; ++i ) { 
            returnArray[returnSize[0]++] = help[i];
        }
    
        free( help );
    
        return returnArray;
    }

来自[英文不好啊][Link 1]

[Link 1]: https://leetcode-cn.com/problems/relative-sort-array/comments/