tag:blogger.com,1999:blog-4731036105252322780.post8484193024006233579..comments2024-03-01T02:55:58.951-08:00Comments on Buttercola: Leetcode: Wiggle Sort IIButter is looking for a jobhttp://www.blogger.com/profile/01481083468821703855noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-4731036105252322780.post-3326397546700927082020-10-11T10:33:29.272-07:002020-10-11T10:33:29.272-07:00This is perfect O(N) & O(1) , time n space com...This is perfect O(N) & O(1) , time n space complexity.<br /><br />public class Solution {<br /><br /> public void wiggleSort(int[] nums) {<br /> int median = findKthLargest(nums, (nums.length + 1) / 2);<br /> int n = nums.length;<br /><br /> int left = 0, i = 0, right = n - 1;<br /><br /> while (i <= right) {<br /><br /> if (nums[newIndex(i,n)] > median) {<br /> swap(nums, newIndex(left++,n), newIndex(i++,n));<br /> }<br /> else if (nums[newIndex(i,n)] < median) {<br /> swap(nums, newIndex(right--,n), newIndex(i,n));<br /> }<br /> else {<br /> i++;<br /> }<br /> }<br /> }<br /><br /> private int findKthLargest(int[] nums, int k) {<br /><br /> k = nums.length - k;<br /> int lo = 0;<br /> int hi = nums.length - 1;<br /> while (lo < hi) {<br /> final int j = partition(nums, lo, hi);<br /> if(j < k) {<br /> lo = j + 1;<br /> } else if (j > k) {<br /> hi = j - 1;<br /> } else {<br /> break;<br /> }<br /> }<br /> return nums[k];<br /> }<br /><br /> private int partition(int[] nums, int left, int right) {<br /><br /> int i = left;<br /> int j = right + 1;<br /> while(true) {<br /> while(i < right && nums[++i] < nums[left]);<br /> while(j > left && nums[left] < nums[--j]);<br /> if(i >= j) {<br /> break;<br /> }<br /> swap(nums, i, j);<br /> }<br /> swap(nums, left, j);<br /> return j;<br /> }<br /><br /> private int newIndex(int index, int n) {<br /> return (1 + 2*index) % (n | 1);<br /> }<br /><br /> private void swap(int[] nums, int i, int j) {<br /> int temp = nums[i];<br /> nums[i] = nums[j];<br /> nums[j] = temp;<br /> }<br /><br />}Anonymoushttps://www.blogger.com/profile/05659122555537367825noreply@blogger.comtag:blogger.com,1999:blog-4731036105252322780.post-80309762256491556382020-07-12T06:25:02.552-07:002020-07-12T06:25:02.552-07:00In the solution using median i.e. this line:
int m...In the solution using median i.e. this line:<br />int median = findMedian(nums, 0, n - 1, (n - 1) / 2);<br /><br />After this line median will be at the correct place. All nums at the left will be smaller than median and on right greater than median.<br />So why are again doing those steps?paritoshhttps://www.blogger.com/profile/13069724440006772697noreply@blogger.comtag:blogger.com,1999:blog-4731036105252322780.post-29661323004407626372017-01-31T20:08:56.161-08:002017-01-31T20:08:56.161-08:00In the alternative solution in-place 3-way partiti...In the alternative solution in-place 3-way partition, on line 31 you are creating a temporary array of size n. How is this O(1) extra space solution when you have used extra space of size n?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4731036105252322780.post-10368403363821770342016-09-30T02:18:08.276-07:002016-09-30T02:18:08.276-07:00Nice Job!!Nice Job!!Anonymoushttps://www.blogger.com/profile/04797138248073743730noreply@blogger.com