Sort (Java) - ShuweiLeung/Thinking GitHub Wiki

1.（324:Medium）（非常经典题）Wiggle Sort II

  • 核心思想：这道题给了我们一个无序数组，让我们排序成摆动数组，满足nums[0] < nums[1] > nums[2] < nums[3]...，并给了我们例子。我们可以先给数组排序，然后在做调整。调整的方法是找到数组的中间的数，相当于把有序数组从中间分成两部分，然后从前半段的末尾取一个，在从后半的末尾去一个，这样保证了第一个数小于第二个数，然后从前半段取倒数第二个，从后半段取倒数第二个，这保证了第二个数大于第三个数，且第三个数小于第四个数，以此类推直至都取完。该方法并不是最优解，但下边的O(n) time and/or in-place with O(1) extra space是在该思路的基础上推导出来的。
  • 该题参考三个链接如下：

Three-way partition

Step by step explanation of index mapping

video演示程序运行过程

  • 参考代码如下：
    public void wiggleSort2(int[] nums) {
       int median = findKthLargest(nums, (nums.length + 1) / 2);
       /*
        * repeated medians can cause problems so it's best to put them as far apart as possible
       在找到中位数以后，数组中中位数以前的数字都大于等于median，中位数以后的数字都小于等于median，之所以从大到小排序，是为了当中位数
       存在多个时，使相邻的两个中位数尽量远，如nums = [4,5,5,6] ，如果将4和5放在index=0和2的位置，把5和6放在1和3的位置，这样并不
       满足Wiggle Sort的要求，两个5相邻且相等。所以在nums partition完以后，nums应变为[5,6,4,5]，这样6和5放在index=1和3位置，
       5和4放在index=0和2位置
       */
       //下面使用three-way partition去重排序,https://en.wikipedia.org/wiki/Dutch_national_flag_problem#Pseudocode
       int n = nums.length;
       int left = 0, right = n - 1;
       int index = 0;
       //Mapped_idx[Left] denotes the position where the next smaller-than median element  will be inserted.
       //Mapped_idx[Right] denotes the position where the next larger-than median element  will be inserted.
       while (index <= right) {
           if (nums[newIndex(index, n)] > median) {
               swap(nums, newIndex(left++, n), newIndex(index++, n)); //要保证index>=left，所以交换完index要++
           } else if (nums[newIndex(index, n)] < median) {
               swap(nums, newIndex(right--, n), newIndex(index, n));
           } else { //当等于中位数的时候，保持对应位置的数字不变即可
               index++;
           }
       }
   }

    private int newIndex(int index, int n) {
        return (1 + 2 * index) % (n | 1);  //保证比median大的数字全部映射到odd index，比median小的数字全部映射到even index
        //n | 1是一个trick，如果是(1+2*index)%n,那映射后的索引可能是1，3，5，1，3，5...的循环，不能遍布所有的数组位置
    }

    //是Leetcode 215题的答案，quick sort中的partition代码
    public int findKthLargest(int[] nums, int k) {
       if (nums == null || nums.length == 0) return 0;
       int left = 0;
       int right = nums.length - 1;
       while (true) {
           int pos = partition(nums, left, right);
           if (pos + 1 == k) {
               return nums[pos];
           } else if (pos + 1 > k) {
               right = pos - 1;
           } else {
               left = pos + 1;
           }
       }
    }

    private int partition(int[] nums, int left, int right) { //注意交换的时候比pivot大的数放在前边，小的放在后边
       int pivot = nums[left];
       int l = left + 1;
       int r = right;
       while (l <= r) {
           if (nums[l] < pivot && nums[r] > pivot) {
               swap(nums, l++, r--);
           }
           if (nums[l] >= pivot) l++;
           if (nums[r] <= pivot) r--;
       }
       swap(nums, left, r);
       return r;
    }

    private void swap(int[] nums, int i, int j) {
       int temp = nums[i];
       nums[i] = nums[j];
       nums[j] = temp;
    }

2.（220:Medium）（非常经典题）Contains Duplicate III

  • 该题利用TreeSet的自动排序特性，并且利用TreeSet自带的两个API，分别是ceiling(E e): Returns the least element in this set greater than or equal to the given element, or null if there is no such element.和floor(E e): Returns the greatest element in this set less than or equal to the given element, or null if there is no such element.
  • 我们维护一个长度最大为k的滑动窗口(利用TreeSet和遍历的索引i来保证)，保证数字的位置范围是在k之内的。更多细节请参考代码实现。

3.（179:Medium）（非常非常经典题）Largest Number

  • The idea here is basically implement a String comparator to decide which String should come first during concatenation. Because when you have 2 numbers (let's convert them into String), you'll face only 2 cases: For example:
String s1 = "9";
String s2 = "31";

String case1 =  s1 + s2; // 931
String case2 = s2 + s1; // 319
  • Apparently, case1 is greater than case2 in terms of value. So, we should always put s1 in front of s2. 换句话说，应使拼接后字符串尽量大的字符串置于前面。
⚠️ **GitHub.com Fallback** ⚠️