leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

sort-colors.dart (1294B)

      1 //Given a list of "colors" represented by the numbers 0 1 and 2
      2 //sort the list. I implemented a merge sort algorithm to
      3 //sort the list.
      4 //The time complexity of my code is O(nlog(n)) because that is
      5 //the time complexity of merge sort.
      6 //Time: 255ms Beats: 70%
      7 //Memory: 143.2MB Beats: 20.83%
      8 class Solution {
      9   void sortColors(List<int> nums) {
     10       List<int> new_nums = merge(nums);
     11       for(int i = 0 ; i < nums.length ; ++i){
     12           nums[i] = new_nums[i];
     13       }  
     14   }
     15   List<int> merge(List<int> nums){
     16       if(nums.length == 1){
     17           return nums;
     18       }
     19       List<int> l1 = merge(nums.sublist(0, (nums.length / 2).toInt()));
     20       List<int> l2 = merge(nums.sublist((nums.length / 2).toInt()));
     21       List<int> l3 = [];
     22       int first_pt = 0;
     23       int second_pt = 0;
     24       while(first_pt < l1.length && second_pt < l2.length){
     25           if(l1[first_pt] < l2[second_pt]){
     26               l3.add(l1[first_pt]);
     27               first_pt += 1;
     28           }
     29           else{
     30               l3.add(l2[second_pt]);
     31               second_pt += 1;
     32           }
     33       }
     34       while(first_pt < l1.length){
     35         l3.add(l1[first_pt]);
     36         first_pt += 1;
     37       }
     38       while(second_pt < l2.length){
     39          l3.add(l2[second_pt]);
     40          second_pt += 1;
     41       }
     42       return l3;
     43   }
     44 }