IVN
0%

Minimum Moves

Posted on Edited on In
Symbols count in article: 5.6k Reading time ≈ 5 mins.

Minimum Moves to Make Equal

215. Kth Largest Element in an Array

https://leetcode.com/problems/kth-largest-element-in-an-array/discuss/2180600/A-Guide-to-Quick-Select-or-JAVA

How Does Quickselect Work?

Quickselect works identical to quicksort in that we:

  • Pick a pivot
  • Partition the data into two where:
    • Numbers less than the pivot go to the left
    • Numbers greater than the pivot go to the right

However, instead of recursing into both sides as in Quicksort, quickselect only recurs into one side; whichever one would have our kth largest element.
The main thing to note here is that our pivot at any given partition will always end up at the correct index. Therefore, we just need to check:

  • If our pivot is at our “kth largest” index, return the number at that index.
  • If our pivot comes before the “kth largest” index, perform quickselect on the right partition.
  • If our pivot comes after the “kth largest” index, perform quickselect on the left partition.
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
public int findKthLargest(int[] nums, int k) {
	return quickSelect(nums, 0, nums.length-1, nums.length-k);
}

private int quickSelect(int[] nums, int left, int right, int k) {
	if (left == right) return nums[left];

	int pIndex = new Random().nextInt(right - left + 1) + left;
	pIndex = partition(nums, left, right, pIndex);

	if (pIndex == k) return nums[k];
	else if (pIndex < k) return quickSelect(nums, pIndex+1, right, k);
	return quickSelect(nums, left, pIndex-1, k);
}

private int partition(int[] nums, int left, int right, int pIndex) {
	int pivot = nums[pIndex];
	swap(nums, pIndex, right);
	pIndex = left;

	for (int i=left; i<=right; i++) 
		if (nums[i] <= pivot) 
			swap(nums, i, pIndex++);

	return pIndex - 1;
}

private void swap(int[] nums, int x, int y) {
	int temp = nums[x];
	nums[x] = nums[y];
	nums[y] = temp;
}

传统快排！

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
Random rand=new Random();
public int findKthLargest(int[] nums, int k) {
    int n=nums.length;
    int low=0;
    int high=n-1;
    while(low<=high){
        int j=partition(nums,low,high);
        if(j<n-k){
            low=j+1;
        }else if(j>n-k){
            high=j-1;
        }else{
            return nums[j];
        }
    }
    return -1;
}

int partition(int[] nums, int start, int end){
    int index=rand.nextInt(end-start+1)+start;
    swap(nums,start,index);
    int pivot=nums[start];
    int i=start+1;
    int j=end;
    //[start,i) <=pivot
    //[i,j] unknown
    //(j,end] >pivot
    while(i<=j){
        if(nums[j]>pivot){
            j--;
        }else{
            swap(nums,i++,j);
        }
    }
    swap(nums,start,j);
    return j;
}

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

462. Minimum Moves to Equal Array Elements II

In one move, you can increment or decrement an element of the array by 1.

https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/discuss/2215782/Visual-Explanation-%2B-Interview-Tips-or-JAVA

Find the Median

Approach 1: Sort

Approach 2: Quick Select

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
57
58
    Random rand=new Random();
    public int minMoves2(int[] nums) {
        int median=kthSmallest(nums,nums.length/2);
        int res=0;
        for (int num : nums) {
            res+=Math.abs(num-median);
        }
        return res;
    }

    int kthSmallest(int[] nums, int k){
        int n=nums.length;
        int left=0;
        int right=n-1;
        while(left<=right){
            int index=partition(nums,left,right);
            if(index==k){
                return nums[index];
            }else if(index<k){
                left=index+1;
            }else{
                right=index-1;
            }
        }
        return -1;
    }

    int partition(int[] nums, int start, int end){
        int index=start+rand.nextInt(end-start+1);
        swap(nums,start,index);
        int left=start+1;
        int right=end;
        int pivot=nums[start];
        //[start+1,left) <=pivot
        //[left,right] unknown
        //(right,end] >pivot
        while(left<=right){
            if(nums[right]>pivot){
                right--;
            }else{
                swap(nums,left++,right);
            }
        }
        swap(nums,start,right);
        return right;
    }

    void swap(int[] nums, int i, int j){
        if(i==j){
            return;
        }
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
/*        a=a^b;
        b=a^b;//a^b^b
        a=a^b; //a^b^a*/
    }

453. Minimum Moves to Equal Array Elements

let’s define sum as the sum of all the numbers, before any moves; minNum as the min number int the list; n is the length of the list;

After, say m moves, we get all the numbers as x , and we will get the following equation

1
sum + m * (n - 1) = x * n

and actually,

1
x = minNum + m

This part may be a little confusing, but @shijungg explained very well. let me explain a little again. it comes from two observations:

  1. the minum number will always be minum until it reachs the final number, because every move, other numbers (besides the max) will be increamented too;
  2. from above, we can get, the minum number will be incremented in every move. So, if the final number is x, it would be minNum + moves;

and finally, we will get

1
sum - minNum * n = m

This is just a math calculation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//sum+m*(n-1)=n*x
//x=minNum+m
//sum+m*(n-1)=n*(minNum+m)
//sum-m=n*minNum
public int minMoves(int[] nums) {
    int n=nums.length;
    int sum=0;
    int min=Integer.MAX_VALUE;
    for (int num : nums) {
        sum+=num;
        min=Math.min(min,num);
    }
    return sum-n*min;
}

2333. Minimum Sum of Squared Difference

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
class Solution {
public:
    long long minSumSquareDiff(vector<int>& nums1, vector<int>& nums2, int k1, int k2) {
        int n = nums1.size();
        vector<int> diff(n);
        for(int i = 0; i<n; ++i) {
            diff[i] = abs(nums1[i] - nums2[i]);
        }
        //max_element() return an iterator pointing to the max element
        //to get the actual value of max element, must use *
        int M = *max_element(diff.begin(), diff.end());
        vector<int> bucket(M+1);
        for(int i = 0 ; i<n; ++i) {
            bucket[diff[i]]++;
        }
        int k = k1 + k2;
        for(int i = M; i > 0; --i) {
            if(bucket[i] > 0) {
                int minus = min(bucket[i], k);
                bucket[i] -= minus;
                //every diff in bucket[i] is decreased by one
                //in turn, they add to diff num in bucket[i-1]
                bucket[i-1] += minus;
                k -= minus;
            }
        }
        long long ans = 0;
        for(long long i = M; i > 0; --i) {
            ans += bucket[i]*i*i;
        }
        return ans;
    }
};