Press "Enter" to skip to content

Posts tagged as “sorting”

花花酱 LeetCode 349. Intersection of Two Arrays

题目大意:求2个数组的交集。

Problem:

https://leetcode.com/problems/intersection-of-two-arrays/description/

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1]nums2 = [2, 2], return [2].

Note:

  • Each element in the result must be unique.
  • The result can be in any order.

C++ using std::set_intersection

C++ hashtable

 

花花酱 LeetCode 506. Relative Ranks

题目大意:给你一些人的分数,让你输出他们的排名,前三名输出金银铜牌。

Problem: 

Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: “Gold Medal”, “Silver Medal” and “Bronze Medal”.

Example 1:

Note:

  1. N is a positive integer and won’t exceed 10,000.
  2. All the scores of athletes are guaranteed to be unique.

Solution 1: Sorting ( + Binary Search)

C++

 

花花酱 LeetCode 791. Custom Sort String

题目大意:给你字符的顺序,让你排序一个字符串。

S and T are strings composed of lowercase letters. In S, no letter occurs more than once.

S was sorted in some custom order previously. We want to permute the characters of T so that they match the order that S was sorted. More specifically, if x occurs before y in S, then x should occur before y in the returned string.

Return any permutation of T (as a string) that satisfies this property.

 

Note:

  • S has length at most 26, and no character is repeated in S.
  • T has length at most 200.
  • S and T consist of lowercase letters only.

Solution 1: HashTable + Sorting

  1. Store the order of char in a hashtable
  2. Sort the string based on the order

Time complexity: O(nlogn)

Space complexity: O(128)

 

花花酱 LeetCode 769. Max Chunks To Make Sorted

题目大意:给你一个0 ~ n-1的排列,问你最多能分成几组,每组分别排序后能够组成0 ~ n-1。

Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], we split the array into some number of “chunks” (partitions), and individually sort each chunk.  After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1:

Example 2:

Note:

  • arr will have length in range [1, 10].
  • arr[i] will be a permutation of [0, 1, ..., arr.length - 1].

Solution 1: Max so far / Set

Time complexity: O(nlogn)

Space complexity: O(n)

C++

 

Solution 2: Max so far

Time complexity: O(n)

Space complexity: O(1)

C++

Java

Python3

 

 

 

花花酱 LeetCode 480. Sliding Window Median

题目大意:让你求移动窗口的中位数。

Problem:

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:

[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Therefore, return the median sliding window as [1,-1,-1,3,5,6].

Note: 
You may assume k is always valid, ie: k is always smaller than input array’s size for non-empty array.



Solution 0: Brute Force

Time complexity: O(n*klogk) TLE 32/42 test cases passed

Solution 1: Insertion Sort

Time complexity: O(k*logk +  (n – k + 1)*k)

Space complexity: O(k)

C++ / vector

C++ / vector + binary_search for deletion.

Java

Java / Binary Search

 

Python

Solution 2: BST

 

Related Problems: