新博文地址:[leetcode]Sort Colors
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.
click to show follow up.
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.
click to show follow up.
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?
暂未想到one-pass的方法
2-pass的比较简单,借助一个hash表即可。
public void sortColors(int[] A) { int[] hash = new int[3]; for(int tem : A){ hash[tem]++; } int index = 0; for(int i = 0; i < 3;i++){ while(hash[i] != 0){ A[index++] = i; hash[i]--; } } }
相关推荐
* [Sort](https://github.com/kamyu104/LeetCode#sort) * [Recursion](https://github.com/kamyu104/LeetCode#recursion) * [Binary Search](https://github.com/kamyu104/LeetCode#binary-search) * [Binary Search...
Colors LeetCode 125 Valid Palindrome LeetCode 167 Two Sum II - Input array is sorted LeetCode 344 Reverse String LeetCode 345 Reverse Vowels of a String 2 字符串 编号 题目 LeetCode 3 Longest Substring...
leetcode怎么销号 LeetCode-Solutions :green_heart:My own LeetCode solutions No. Problem LeetCode 力扣 Python Go Solution Difficulty Tag 0017 Letter Combinations of a Phone ...Sort Colors M
_75_SortColors_twopointer _142_LinkedListCycle2_twopointer //////// 弗洛伊德循环检测 _287_FindtheDuplicateNumber_TwoPointer_Floyd _340_LongestSubstringwithAtMostKDistinctCharacters_TwoPointer _424_...
Colors Leetcode 215. Kth Largest Element Leetcode 4. Median of Two Sorted Arrays 注意:后两题是与快速排序非常相似的快速选择(Quick Select)算法,面试中很常考 链表类(Linked List): 基础知识:链表如何...
Leetcode经典01背包 algo 1. 数据结构与算法 数组,链表,(串和序列) 堆,栈,队列 树,图 排序,搜索 贪心,回溯,动态规划 堆:一种完全二叉树,任意节点大于左右孩子(大顶堆...Colors 计数排序 | | | 88 Merge So
扩展矩阵leetcode Leetcode Leetcode Answer-Java 数组 11.乘最多水容器 maxArea 26.删除排序数组中的重复项 removeDuplicates 33.搜索旋转排序数组 ...sortColors 179.最大数 largestNumber 324.摆
SortColors 167 - TwoSum2 DCP 75 是一个双指针问题,如果当前项为 0,则使用 p1 p2 指向开始和结束,然后与开始交换,如果当前项目为 2,则与结束交换。 167是同一个想法 02/01/2020 16 -3SumClosest 344 - Reverse...
leetcode中国 每周小测 每周题目 week 1 adjust : 将数组中指定索引处的值替换为经函数变换的值 实现版本: ramda版本参考: groupAnagrams ...给定一个字符串数组,将字母异位词组合在一起。...sortColors
排序颜色: ://leetcode.com/problems/sort-colors/ 3index,nums [0-zero] = 0,nums [zero + 1,two-1] = 1,nums [two-n] = 2,用3个索引,nums [0-zero] = 0,nums [零+1,two-1] = 1,nums [two-n] = 2,初始...
sortcolors: 对三种颜色的方块排序 water: 不同高度的台阶,能够蓄水多少 quicksort: 面试必考之一,快速排序 heapsort: 堆排序算法 B+tree: B+树 RedBlackTree:红黑树 AVLTree: 自平衡的二叉查找数 Dijkstra:最短...
leetcode中国 leetcode-study 地址: 考虑维度 时间维度:是指执行当前算法所消耗的时间,我们通常用「时间复杂度」来描述。 空间维度:是指执行当前...SortColors 贪心思想 给小孩分配饼干,最多分配多少个 AssignCook
leetcode卡Leetcode-解决方案 LeetCode DS 日常挑战的解决方案 问题陈述 1.InvertBinaryTree - 2.子序列- 3.SearchInsertPosition - 4.SortColors - 5.单号——
(Sort_Colors) 重复和缺失号码 (Repeat_And_Missing_Number) 在没有额外空间的情况下合并两个已排序的数组 (Merge_Sorted_Arrays) Kadane 的算法 (Kadane's_Algorithm) 合并重叠子区间(Merge_Overlapping_SubInterv)...
Sort Colors Kth Largest Element in an Array 桶排序 First Missing Positive 计数排序 H-Index 基数排序 Maximum Gap 其他 Largest Number 小结 查找 Search for a Range Search Insert Position Search in ...