Posts

Showing posts with the label bucket sort

AM 400. Maximum Gap

Code ( Language :C++) ( Judger :cloudjudge-cluster-4) Edit class Solution { public : /** * @param nums: an array of integers * @return: the maximun difference */ int maximumGap ( vector < int > &nums) { // write your code here // O(n) bucket sort // 思想就是分组,然后不是各元素比较,二是组比较 // 1,找到最大值,最小值 // 2, 所要找的GAP >= (max - min) / size +1,即平均的GAP。 // 如果每个bucket的容量是这个平均GAP, // 所要的bucket个数是 (max - min) / 平均GAP。 // 3, 遍历数组,判断每个元素属于哪个bucket。 // 每个bucket中只需要存属于该bucket的最大和最小值。 // 4, potential的最大GAP是相邻两个bucket的最小和最大值之差。 // maxGap一定是大于或等于avg的,所以maxGap不会出现在bucket里面,二是两个bucket之间。 const int size = nums.size(); if (size < 2 ){ return 0 ; } int minVal = INT_MAX; int maxVal = INT_MIN; for ( auto i : nums){ minVal = min(minVal, i); maxVal = max(maxVal, i); ...

bucket sort一个萝卜一个坑 类型

缘起: 一般这种类型的题目都可以用大于O(1)的时间复杂度或空间复杂度轻松解出。要实现O(1)就要用bucket sort 思想,把原vector里的value转换至 bucket 的index,一般题目中会推演出 value和index的关系。在新的vector也就是 bucket中,value值会是对应原来vector value的元素个数或其他数值。 步骤: 1,建立bucket array。 2,根据建立好的bucket array,求解最后答案。 坑点: 1,注意判断原数组的value值是否超出 bucket array index范围。 2, A[i] != A[A[i] - 1 ],避免用 A[i] != i + 1这种错误。 1304. H-Index Facebook2 1095. Maximum Swap 1025. Custom Sort String 189. First Missing Positive / unsorted,一个萝卜一个坑的问题。index 位置上对应的值如果不是index + 1, 就是missing。所以,第一步是把各个值放到应该的位置上,比如2,应该放在index 1 位置。 // 一个重要关系是A[i] = A[A[i] - 1], 类似于bucket sort,填坑 Code ( Language :C++) ( Judger :cloudjudge-cluster-4) Edit class Solution { public : /** * @param A: An array of integers * @return: An integer */ int firstMissingPositive ( vector < int > &A) { // write your code here // 1 - n const int n = A.size(); for ( int i = 0 ; i < n; i++){ while (A[i] ...

189. First Missing Positive

// unsorted,一个萝卜一个坑的问题。index 位置上对应的值如果不是index + 1, 就是missing。所以,第一步是把各个值放到应该的位置上,比如2,应该放在index 1 位置。 // 一个重要关系是A[i] = A[A[i] - 1], 类似于bucket sort,填坑 Code ( Language :C++) ( Judger :cloudjudge-cluster-4) Edit class Solution { public : /** * @param A: An array of integers * @return: An integer */ int firstMissingPositive ( vector < int > &A) { // write your code here // 1 - n const int n = A.size(); for ( int i = 0 ; i < n; i++){ while (A[i] <= n && A[i] >= 1 && A[i] != A[A[i] - 1 ]){ //这里不能用 i + 1 啊,比如存在重复的[1,1],死循环了。用A[i] != A[A[i] - 1] int tmp = A[i]; A[i] = A[A[i] - 1 ]; A[tmp - 1 ] = tmp; } } for ( int i = 0 ; i < n; i++){ if (A[i] != i + 1 ){ return i + 1 ; } } return n + 1 ; } };

Facebook2 1095. Maximum Swap

Given a non-negative integer. You could choose to swap two digits of it. Return the maximum valued number you could get. The given number is in the range of [0, 10^8] Have you met this question in a real interview?    Yes Problem Correction Example Example 1: Input: 2736 Output: 7236 Explanation: Swap the number 2 and the number 7. Example 2: Input: 9973 Output: 9973 Explanation: No swap. Code ( Language :C++) Edit class Solution { public : /** * @param num: a non-negative intege * @return: the maximum valued number */ int maximumSwap ( int num) { // Write your code here if (num < 10 ){ return num; } string s = to_string(num); std :: vector < int > arr( 10 , -1 ); // map to index for ( int i = 0 ; i < s.size(); i++){ arr[s[i] - '0' ] = i; } for ( int i = 0 ; i < s.size(); i++){ ...

1025. Custom Sort String

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. 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. Have you met this question in a real interview?    Yes Problem Correction Example Example : Input: S = "cba" T = "abcd" Output: "cbad" Explanation: "a", "b", "c" appear in S, so the order of "a", "b", "c" should be "c", "b", and "a". Since "d" does not appea...

1304. H-Index

Description 中文 English Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index. According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each." If there are several possible values for h, the maximum one is taken as the h-index. Have you met this question in a real interview?    Yes Problem Correction Example given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3. O(N)的思路 class Solution { public : /** * @param citations: a list of integers * @return: return a int...