Greedy algorithms are usually given in leetcode style technical interviews.They involve taking the maximum or minimum.Below is a an example of using the greedy approach to solve a problem.
Problem
Given an integer array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
You may assume the input array always has a valid answer.
Example 1:
Input: nums = [1,5,1,1,6,4]
Output: [1,6,1,5,1,4]
Explanation: [1,4,1,5,1,6] is also accepted.
Example 2:
Input: nums = [1,3,2,2,3,1]
Output: [2,3,1,3,1,2]
Constraints:
.1 <= nums.length <= 5 * 104
.0 <= nums[i] <= 5000
.It is guaranteed that there will be an answer for the given input nums.
Discussion
This algorithm can be solved using the greedy approach.We copy the contents of the original array into a new one and sort it.We create two pointers. One is placed at the end of the new array,the other in the middle of it.We iterate through the original from the start.If the index is even,we take the value from the second pointer.Otherwise,we take the value from the first one.This ensures that the biggest values are always placed at the odd indexes.
Solution
Java
class Solution {
public void wiggleSort(int[] nums) {
int [] nums1= new int [nums.length];
for(int i=0;i<nums.length;i++)nums1[i]=nums[i];
Arrays.sort(nums1);
int nums1Index=nums.length-1;
int nums1Index1=(nums.length-1)/2;
for(int i=0;i<nums.length;i++){
if(i%2==0)nums[i]=nums1[nums1Index1--];
else nums[i]=nums1[nums1Index--];
}
return;
}
}
C#
public class Solution {
public void WiggleSort(int[] nums) {
int [] nums1= new int [nums.Length];
for(int i=0;i<nums.Length;i++)nums1[i]=nums[i];
Array.Sort(nums1);
int nums1Index=nums.Length-1;
int nums1Index1=(nums.Length-1)/2;
for(int i=0;i<nums.Length;i++){
if(i%2==0)nums[i]=nums1[nums1Index1--];
else nums[i]=nums1[nums1Index--];
}
return;
}
}
C++
class Solution {
public:
void wiggleSort(vector<int>& nums) {
vector<int> nums1;
for(int i=0;i<nums.size();i++)nums1.push_back(nums[i]);
std::sort(nums1.begin(),nums1.end());
int nums1Index=nums.size()-1;
int nums1Index1=(nums.size()-1)/2;
for(int i=0;i<nums.size();i++){
if(i%2==0)nums[i]=nums1[nums1Index1--];
else nums[i]=nums1[nums1Index--];
}
return;
}
};