2019年8月9日 星期五

[LeetCode] 1122. Relative Sort Array 解題思路 (Easy)



這題 LeetCode 非常有趣,題目說給一個 arr1 和一個 arr2 , arr2 每個元素都不一樣,然後 arr2 的每個元素都有在 arr1 之中。

請排序 arr1 結果跟 arr2 一樣,剩下不一樣的數字則按照升冪排序。




LeetCode 題目連結




題目


Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all elements in arr2 are also in arr1.
Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in arr2.  Elements that don't appear in arr2 should be placed at the end of arr1 in ascending order.

Example 1:
Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]

Constraints:
  • arr1.length, arr2.length <= 1000
  • 0 <= arr1[i], arr2[i] <= 1000
  • Each arr2[i] is distinct.
  • Each arr2[i] is in arr1.

Accept 作法


我的作法很長,因為想不依賴其他資料型態,用最原始的 IntArray 去操作。
Runtime: 200ms
Memory: 35.3mb

Kotlin
class Solution {
    fun relativeSortArray(arr1: IntArray, arr2: IntArray): IntArray {
        val result = IntArray(arr1.size)
        val remainingElements = IntArray(arr1.size - arr2.size)     
        var remainIndex = 0
        var resultIndex = 0
        
        //由第二個 array 一個一個比對第一個 array, 為了一樣的順序
        for(j in 0..arr2.size-1){
            for(i in 0..arr1.size - 1){
                if(arr1[i] == arr2[j]){
                    result[resultIndex] = arr1[i]
                    resultIndex++
                }
                
            }
            
          
        }
        
        //由第一個 array 去比對第二個 array, 只為了找出不一樣的數字
         for(i in 0..arr1.size - 1){
             var isSame = false
             for(j in 0..arr2.size-1){
                  if(arr1[i] == arr2[j]){
                      isSame = true
                      break
                  }
             }
             
             if(!isSame){
                 remainingElements[remainIndex]=arr1[i]
                 remainIndex++
                 
             }
         }
         
         //剩下不一樣的數字 array 給他正確的 size, 避免之後多餘的 size 有 0 會干擾結果
         var realSizeRemainingArray = IntArray(remainIndex)
         for(i in 0..realSizeRemainingArray.size - 1){
             realSizeRemainingArray[i] = remainingElements[i]
         }
         realSizeRemainingArray.sort(0,realSizeRemainingArray.size)
         
         var indexForResult = result.size - remainIndex
         for(i in 0..remainingElements.size-1){
             if(indexForResult< result.size){
                     result[indexForResult] = realSizeRemainingArray[i]
                     indexForResult++
             }
              
         }
         
        return result
    }
}



更多 LeetCode 相關資源


複習程式面試書籍


除了 LeetCode 練習外,我也入手了這本,題庫來自真正的面試,並非摘自教科書。它們反映出頂尖公司真正會出的題目,你可以藉此做好充分準備

需要的話可以看看,寫得很仔細。



書名:提升程式設計師的面試力:189道面試題目與解答




相關 LeetCode文章一律會放在 程式解題 標籤分類,歡迎持續追蹤。


1 則留言:

  1. creativity of writer is purely impressive. It has touched to the level of expertise with his writing. Everything is up to the mark. Written perfectly and I can use such information for my coming assignment. canvs

    回覆刪除