数组与贪心算法——215、75、324、517（3中1难）

215. 数组中的第K个最大元素(中等)

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

解法一、桶排

塞进数组然后从高往低遍历，4n怎么不是n

class Solution {
    public static int findKthLargest(int[] nums, int k) {
		int[] numNum = new int[20001];
		int max = Integer.MIN_VALUE;
		for(int num : nums){
			numNum[num+10000]++;
			max = Math.max(num,max);
		}
		for(int i = max+10000;i >=0 ;i--){
			if(k <= numNum[i + 10000]){
				return i;
			}else{
				k -= numNum[i+10000];
			}
		}
		return 0;
    }
}

解法二、线性快排

相较于排序的传统快排，它在意的并非顺序，而是在第k个位置上的元素。此外，也不需要双序递归，只要通过k和i、j的比较，选择下一个循环区间。

class Solution {
    // quickselect 函数用于在数组的索引 l 到 r 之间找到第 k 小的元素
    int quickselect(int[] nums, int l, int r, int k) {
        // 如果范围内只有一个元素，直接返回第 k 个元素
        if (l == r) return nums[k];
        
        // 选择当前范围的第一个元素作为枢轴
        int x = nums[l], i = l - 1, j = r + 1;
        
        // 分区循环：继续右移 i 和左移 j，交换相对于枢轴顺序错误的元素
        while (i < j) {
            // 增加 i，直到找到一个大于等于枢轴的元素
            do i++; while (nums[i] < x);
            
            // 减少 j，直到找到一个小于等于枢轴的元素
            do j--; while (nums[j] > x);
            
            // 如果 i 仍然在 j 的左侧，交换 i 和 j 位置的元素
            if (i < j) {
                int tmp = nums[i]; // 暂存 i 位置的元素
                nums[i] = nums[j]; // 把 j 位置的元素移动到 i
                nums[j] = tmp; // 把 i 位置的元素移动到 j
            }
        }
        
        // 如果 k 位于左分区，递归调用 quickselect 在左分区中查找
        if (k <= j) return quickselect(nums, l, j, k);
        
        // 否则，递归调用 quickselect 在右分区中查找
        else return quickselect(nums, j + 1, r, k);
    }
    
    // findKthLargest 函数用于找到数组中第 k 大的元素
    public int findKthLargest(int[] _nums, int k) {
        int n = _nums.length; // 获取数组长度
        // 使用 quickselect 找到第 n - k 小的元素（即第 k 大的元素）
        return quickselect(_nums, 0, n - 1, n - k);
    }
}

解法三、大根堆

建一个堆，然后删除k-1次

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int heapSize = nums.length;
        buildMaxHeap(nums, heapSize);
        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
            swap(nums, 0, i);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }

    public void buildMaxHeap(int[] a, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

    public void maxHeapify(int[] a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a, i, largest);
            maxHeapify(a, largest, heapSize);
        }
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/kth-largest-element-in-an-array/solutions/307351/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

75. 颜色分类(中等)

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

进阶：

• 你能想出一个仅使用常数空间的一趟扫描算法吗？

解法一、统计

三个int统计分别的数量，然后一次扫描全部重置。比较好写就不写了

解法二、单指针

用一个ptr维护头部的位置，在第一次遍历的时候，从0到头部都是0，遇到0则往头部交换，然后头部扩充；第二次遍历的时候，遇到1则往头部交换，这样自然地把2往后滤。

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int ptr = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ++ptr;
            }
        }
        for (int i = ptr; i < n; ++i) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ++ptr;
            }
        }
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/sort-colors/solutions/437968/yan-se-fen-lei-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解法三、双指针

遇0则左换，遇2则右换，i到达right的时候停止for循环

class Solution {
    public void sortColors(int[] nums) {
		int left = -1,right = nums.length;
		for(int i = 0;i < right;i++){
			if(nums[i] == 0){
				swap(nums,left+1,i);
				left++;
			}else if(nums[i] == 2){
				swap(nums,right-1,i);
				right--;
                i--;
			}
		}
    }
	private void swap(int[]nums,int i,int j){
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}
}

324. 摆动排序 II（中等）

给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。

你可以假设所有输入数组都可以得到满足题目要求的结果。

解法一、排序再映射

从小到大映射摆放奇数位置，然后映射摆放偶数位置。桶排也是同样的道理（桶排更快，时间击败96%）

别的办法摆了 哥们看不懂

class Solution {
		boolean da = false;
	public void wiggleSort(int[] nums) {
		Arrays.sort(nums);
		int[] res = new int[nums.length];
		for(int i = 0;i < nums.length;i++){
			if(i % 2 == 0){
				res[i] = nums[(nums.length-1)/2 - i/2];
			}else{
				res[i] = nums[nums.length - 1 - i/2];
			}
		}
		for(int i = 0;i < nums.length;i++){
			nums[i] = res[i];
		}
	}
}

class Solution {
    static int N = 5010;
    static int[] bucket = new int[N];
    public void wiggleSort(int[] nums) {
        Arrays.fill(bucket, 0);
        for (int i : nums) bucket[i]++;
        int n = nums.length;
        int j = N - 1;
        //按数组元素从大到小分配
        //先从小到大分配奇数位序
        for (int i = 1 ; i < n ; i += 2) {
            while(bucket[j] == 0) j--;
            nums[i] = j;
            bucket[j]--;
        }
        //再从小到大分配偶数位序
        for (int i = 0 ; i < n ; i += 2) {
            while(bucket[j] == 0) j--;
            nums[i] = j;
            bucket[j]--;
        }
    }
}

517. 超级洗衣机（困难）

假设有 n 台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。

在每一步操作中，你可以选择任意 m (1 <= m <= n) 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。

给定一个整数数组 machines 代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的 最少的操作步数 。如果不能使每台洗衣机中衣物的数量相等，则返回 -1 。

解法一、贪心 模拟水流

for循环可以按上面也可以按下面写，本质上一样的

把所有洗衣机灵活分为AB两组，即[0-i,i+1-n]。对于三个数的max比较，ans是之前最大值，sum绝对值是从A区要往B区（或者反过来）运的数量，num是A区内自己要运的数量。那么，为什么num不取绝对值呢？因为A对B区要运的话，是只能一次一次运出（或者运回）的，此时正负号都在答案的角度来说一样；但A区内部运的话，一个多的洗衣机一次运给一个少的洗衣机，一个少的洗衣机却能同时被两个多的洗衣机运，所以此时只要考虑运出（也就是正的num）就可以了。

反正也不是自己写的，就不放时间空间复杂度图了（

class Solution {
    public int findMinMoves(int[] machines) {
        int tot = Arrays.stream(machines).sum();
        int n = machines.length;
        if (tot % n != 0) {
            return -1;
        }
        int avg = tot / n;
        int ans = 0, sum = 0;
        for (int num : machines) {
            num -= avg;
            sum += num;
            ans = Math.max(ans, Math.max(Math.abs(sum), num));
        }
        return ans;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/super-washing-machines/solutions/1022639/chao-ji-xi-yi-ji-by-leetcode-solution-yhej/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

			int carry = 0;
			int max = 0;
			for(int i = 0; i < machines.length; i++){
				carry = carry + avg - machines[i];
				max = Math.max(max, Math.abs(carry));
				max = Math.max(max, machines[i] - avg);
			}

碎碎念

• 一上学是真的开始感觉刷题的时间变少了很多orz其实现在还没有特别理解贪心 感觉有点脑筋急转弯