算法拾遗-快排与归并

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution {
    public static int[] help = new int[MAX_N];
    public int[] sortArray(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }
    public void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int middle = left + (right - left) / 2;
        mergeSort(nums, left, middle);
        mergeSort(nums, middle + 1, right);
        merge(nums, left, middle, right);
    }
    public void merge(int[] nums, int left, int middle, int right) {
        int i = left;
        int j = middle + 1;
        int index = left;
        while (i <= middle && j <= right) {
            if (nums[i] < nums[j]) {
                help[index] = nums[i];
                index++;
                i++;
            } else {
                help[index] = nums[j];
                index++;
                j++;
            }
        }
        while (i <= middle) {
            help[index++] = nums[i++];
        }
        while (j <= right) {
            help[index++] = nums[j++];
        }
        for (int k = left; k <= right; k++) {// 拷贝回原数组
            nums[k] = help[k];
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

class Solution {
    private static int[] help = new int[500001];

    public int reversePairs(int[] nums) {
        return count(nums, 0, nums.length - 1);
    }

    public int count(int[] nums, int left, int right) {
        if (left == right) {
            return 0;
        }
        int middle = left + (right - left) / 2;
        int leftPairs = count(nums, left, middle);// 左范围答案
        int rightPairs = count(nums, middle + 1, right);// 右范围答案
        int crossPairs = merge(nums, left, middle, right);// 跨越左右产生的答案
        return leftPairs + rightPairs + crossPairs;
    }

    private int merge(int[] nums, int left, int middle, int right) {
        // count 此时左右两边已经有序,对于计算符合要求的值来说更加方便了
        int ii = left;
        int jj = middle + 1;
        int res = 0;
        int sum = 0;
        for (int i = ii; i <= middle; i++) {
            while (jj <= right && (long) nums[i] > (long)2 * nums[jj]) {
                sum += 1;
                jj++;
            }
            res += sum;
        }
        // sort
        int i = left;
        int j = middle + 1;
        int index = left;
        while (i <= middle && j <= right) {
            if (nums[i] < nums[j]) {
                help[index++] = nums[i];
                i++;
            } else {
                help[index++] = nums[j];
                j++;
            }
        }
        while (i <= middle) {
            help[index++] = nums[i++];
        }
        while (j <= right) {
            help[index++] = nums[j++];
        }
        for (int k = left; k <= right; k++) {
            nums[k] = help[k];
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;

    }
    public void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int middle = partition(nums, start, end);
        quickSort(nums, start, middle - 1);
        quickSort(nums, middle + 1, end);
    }
    /**
    /* slow - 1永远满足<= pivot这个特性
    /*slow-1表示<=pivot的区域 slow表示第一个大于pivot的区域
    */
    public int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        int pivotIndex = 0;
        int slow = left;
        for (int i = left; i <=right; i++) {
            if (nums[i] <= pivot) {
                int temp = nums[i];
                nums[i] = nums[slow];
                nums[slow] = temp;
                if (nums[slow] == pivot) {
                    pivotIndex = slow;
                }
                slow++;
            }
        }
        int temp1 = nums[slow - 1];
        nums[slow - 1] = nums[pivotIndex];
        nums[pivotIndex] = temp1;
        return slow - 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Solution {
    public static int first, last;
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
    public void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        partition1(nums, start, end);
        int left1 = first;
        int right1 = last;
        quickSort(nums, start, left1 - 1);
        quickSort(nums, right1 + 1, end);
    }
	/**
	/* first - 1永远满足<pivot这个特性
	/*first表示第一个与大于等于pivot的区域 last表示最后一个大于等于pivot的区域
	*/
    public void partition1(int[] nums, int left, int right) {
        int pivotIndex = left + (int) (Math.random() * (right - left + 1));
        int pivot = nums[pivotIndex];
        first = left;
        last = right;
        int i = left;
        while (i <= last) {
            if (nums[i] < pivot) {
                int temp = nums[i];
                nums[i] = nums[first];
                nums[first] = temp;
                i++;
                first++;
            } else if (nums[i] == pivot) {
                i++;
            } else {
                int temp2 = nums[i];
                nums[i] = nums[last];
                nums[last] = temp2;
                last--;
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // N个元素 第K大 第N - K + 1小
        // 0-N-1 第K大 第N - K小
        return  findKthSmall(nums, nums.length - k);
    }
    
    public int findKthSmall(int[] nums, int k) {
        int ans = 0;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            partition(nums, left, right);
            if (k < first) {
                right = first - 1;
            } else if (k > last) {
                left = last + 1;
            } else {
                ans = nums[first];
                return ans;
            }
        }
        return ans;
    }
    
    public static int first, last;
    public void partition(int[] nums, int left, int right) {
        int pivot = nums[left + (int) Math.random() * (right - left + 1)];
        first = left;
        last = right;
        int i = left;
        while (i <= last) {
            if (nums[i] < pivot) {
                int temp1 = nums[i];
                nums[i] = nums[first];
                nums[first] = temp1;
                first++;
                i++;
            } else if (nums[i] > pivot) {
                int temp2 = nums[i];
                nums[i] = nums[last];
                nums[last] = temp2;
                last--;
            } else {
                i++;
            }
        }
    }
}