Sorting and Searching Part 1 - Medium

Sort Colors

class Solution {
    public void sortColors(int[] nums) {
        int l = 0;
        int cur = 0;
        int r = nums.length - 1;
        
        int tmp;
        
        while (cur <= r) {
            if (nums[cur] == 0) {
                tmp = nums[l];
                nums[l++] = nums[cur];
                nums[cur++] = tmp;
            } else if (nums[cur] == 2) {
                tmp = nums[cur];
                nums[cur] = nums[r];
                nums[r--] = tmp; 
            } else {
                cur++;
            }
        }
    }
}

Top K Frequent Elements

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        
        Map<Integer, Integer> m = new HashMap<Integer, Integer>();
        
        for (int i = 0; i < nums.length; i++) {
            m.put(nums[i], m.getOrDefault(nums[i], 0) + 1);
        }
        
        Queue<Integer> q = new PriorityQueue<Integer>((n1, n2) -> m.get(n1) - m.get(n2));
        
        for (int n : m.keySet()) {
            q.add(n);
            
            if (q.size() > k) q.poll();
        }
        
        int[] result = new int[k];
        
        for (int j = k - 1; j >= 0; j--) {
            result[j] = q.poll();
        }
        
        return result;
        
    }
}

Kth Largest Element in an Array

Arrays.sort(nums);
return nums[k];

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Queue<Integer> q = new PriorityQueue<Integer>((n1, n2) -> n1 - n2);
        
        for (int i = 0; i < nums.length; i++) {
            q.add(nums[i]);
            
            if (q.size() > k) {
                q.poll();
            }
        }
        
        return q.poll(); 
    }
}

위에 문제와 비슷하네요

import java.util.Random;
class Solution {
  int [] nums;

  public void swap(int a, int b) {
    int tmp = this.nums[a];
    this.nums[a] = this.nums[b];
    this.nums[b] = tmp;
  }


  public int partition(int left, int right, int pivot_index) {
    int pivot = this.nums[pivot_index];
    // 1. move pivot to end
    swap(pivot_index, right);
    int store_index = left;

    // 2. move all smaller elements to the left
    for (int i = left; i <= right; i++) {
      if (this.nums[i] < pivot) {
        swap(store_index, i);
        store_index++;
      }
    }

    // 3. move pivot to its final place
    swap(store_index, right);

    return store_index;
  }

  public int quickselect(int left, int right, int k_smallest) {
    /*
    Returns the k-th smallest element of list within left..right.
    */

    if (left == right) // If the list contains only one element,
      return this.nums[left];  // return that element

    // select a random pivot_index
    Random random_num = new Random();
    int pivot_index = left + random_num.nextInt(right - left); 
    
    pivot_index = partition(left, right, pivot_index);

    // the pivot is on (N - k)th smallest position
    if (k_smallest == pivot_index)
      return this.nums[k_smallest];
    // go left side
    else if (k_smallest < pivot_index)
      return quickselect(left, pivot_index - 1, k_smallest);
    // go right side
    return quickselect(pivot_index + 1, right, k_smallest);
  }

  public int findKthLargest(int[] nums, int k) {
    this.nums = nums;
    int size = nums.length;
    // kth largest is (N - k)th smallest
    return quickselect(0, size - 1, size - k);
  }
}

원래 가져왔던 루션이 -- Quicksort

Find Peak Element

class Solution {
    public int findPeakElement(int[] nums) {
        
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i+1]) {
                return i;
            }
        }
        
        return nums.length - 1;
    }
}

그냥 한방에~~

public class Solution {
    public int findPeakElement(int[] nums) {
        return search(nums, 0, nums.length - 1);
    }
    public int search(int[] nums, int l, int r) {
        if (l == r)
            return l;
        int mid = (l + r) / 2;
        if (nums[mid] > nums[mid + 1])
            return search(nums, l, mid);
        return search(nums, mid + 1, r);
    }
}

binary search!!! 이거 냅다 외우자

class Solution {
    public int findPeakElement(int[] nums) {
        
        if (nums.length == 0) return 0; 
        
        int prev = nums[0];
        int loc = 0;
        boolean isIncrease = false; 
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < prev && isIncrease) {
                return i - 1;
            } else if (nums[i] > prev) {
                isIncrease = true; 
                loc = i; 
            } else if (nums[i] < prev) {
                isIncrease = false;
            }
            prev = nums[i];
        }
        
        if (isIncrease) return loc;
        else return 0; 
    }
}

내가 전에 풀었던 방식

Find First and Last Positions of Element in Sorted Array

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return new int[]{-1, -1};
        }
        int start = first(nums, target);
        if (start == nums.length || nums[start] != target) {
            return new int[]{-1, -1};
        }
        int end = first(nums, target + 1);
        return new int[]{start, nums[end] == target? end: end-1};
    }

    public int first(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low + 1 < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] < target) {
                low = mid;
            } else {
                high = mid;
            }
        }
        if (nums[low] == target) {
            return low;
        }
        return high;
    }
}

binary search