Nine Chapter
  • Introduction
    • Summary
  • 1.Binary Search
    • Introduction
    • 458.Last position of target
    • 600.Smallest Rectangle Enclosing Black Pixels
    • 585.Maximum Number in Mountain Sequence
    • 183.Wood Cut
    • 62.Search in Rotated Sorted Array
    • 63.Search in Rotated Sorted Array II
    • 159.Find Minimum in Rotated Sorted Array
    • 160.Find Minimum in Rotated Sorted Array II
    • 75.Find Peak Element
    • 60.Search Insert Position
    • 28.Search a 2D Matrix
    • 240. Search a 2D Matrix II
    • 14.First Position of Target
    • 74.First Bad Version
    • 875. Koko Eating Bananas
    • 1011. Capacity To Ship Packages Within D Days (M)
    • 410. Split Array Largest Sum (H)
    • 475. Heaters (M)
    • 1044. Longest Duplicate Substring (H)
  • 2.Binary Tree
    • Summary
      • 二叉树八股文：递归改迭代
      • BST
      • Frame
    • 66.Binary Tree Preorder Traversal
    • 67.🌟Binary Tree Inorder Traversal
    • 145. Binary Tree Postorder Traversal (E)
    • 98.Validate Binary Search Tree(M)
    • 85.Insert Node in a Binary Search Tree
    • 104. Maximum Depth of Binary Tree(E)
    • 235. Lowest Common Ancestor of a Binary Search Tree (E)
    • 236.Lowest Common Ancestor of Binary Tree(M)
    • 578.Lowest Common Ancestor III
    • 1120.Subtree with Maximum Average
    • 596.Minimum Subtree
    • 480.Binary Tree Paths
    • 453.Flatten Binary Tree to Linked List
    • 110.Balanced Binary Tree
    • 376.Binary Tree Path Sum
    • 246.Binary Tree Path Sum II
    • 475.Binary Tree Maximum Path Sum II
    • 124.Binary Tree Maximum Path Sum (H)
    • Path Sum (*)
      • 112. Path Sum
      • 113. Path Sum II
      • 437. Path Sum III
    • 177.Convert Sorted Array to Binary Search Tree With Minimal Height
    • 7.Binary Tree Serialization
    • 72,73.Construct Binary Tree
    • Binary Search Tree Path
    • 245.Subtree
    • 469.Identical Binary Tree
    • 87.Remove Node in Binary Search Tree
    • 116.Populating Next Right Pointers in Each Node (M)
    • 114. Flatten Binary Tree to Linked List(M)
    • 654.Maximum Binary Tree (M)
    • 105. 🌟Construct Binary Tree from Preorder and Inorder Traversal (M)
    • 106. Construct Binary Tree from Inorder and Postorder Traversal (M)
    • 652. Find Duplicate Subtrees(M)
    • 230. Kth Smallest Element in a BST (M)
    • 538&1038. Convert BST to Greater Tree
    • 450. Delete Node in a BST (M)
    • 701. Insert into a Binary Search Tree (M)
    • 96. Unique Binary Search Trees
    • 95. Unique Binary Search Trees II (M)
    • 1373. Maximum Sum BST in Binary Tree (H)
    • 297. Serialize and Deserialize Binary Tree (H)
    • 222. Count Complete Tree Nodes (M)
    • 1120. Maximum Average Subtree
    • 341. Flatten Nested List Iterator
    • 333. Largest BST Subtree (M)
    • 543. Diameter of Binary Tree
    • Binary Tree Longest Consecutive Sequence(*)
      • 298.Binary Tree Longest Consecutive Sequence
      • 549. Binary Tree Longest Consecutive Sequence II (M)
  • 3.Breadth First Search
    • Introduction
      • BFS 算法解题套路框架
      • 双向 BFS 优化
    • 102.Binary Tree Level Order Traversal (M)
    • 103. Binary Tree Zigzag Level Order Traversal (M)
    • 107.Binary Tree Level Order Traversal II(M)
    • 618.Search Graph Nodes
    • 207.Course Schedule (M)
    • 210.Course Schedule II (M)
    • 611.Knight Shortest Path
    • 598.Zombie in Matrix
    • 133.Clone Graph (M)
    • 178.Graph Valid Tree
    • 7.Binary Tree Serialization
    • 574.Build Post Office
    • 573.Build Post Office II
    • 127.Topological Sorting
    • 127.Word Ladder
    • 126. Word Ladder II
    • (LeetCode)515.Find Largest Value in Each Tree Row
    • 111. Minimum Depth of Binary Tree (E)
    • 752. Open the Lock
    • 542. 01 Matrix (M)
    • 1306. Jump Game III (M)
  • 4.Depth First Search+BackTracking
    • Summary
      • FloodFill 算法
    • 136.Palindrome Partitioning
    • 39.Combination Sum
    • 40.Combination Sum II
    • 377. Combination Sum IV
    • 77.Combinations (M)
    • 78.Subsets (M)
    • 90.Subsets II (M)
    • 46.🌟Permutations
    • 47.Permutations II
    • 582.Word Break II
    • 490.The Maze (M)
    • 51.N-Queens (H)
    • 52. N-Queens II (H)
    • 698. Partition to K Equal Sum Subsets (M)
    • 22. Generate Parentheses (M)
    • 岛屿问题
      • 200.Number of Islands (M)
      • 1254. Number of Closed Islands (M)
      • 1020. Number of Enclaves (M)
      • 695. Max Area of Island (M)
      • 1905. Count Sub Islands (M)
      • 694. Number of Distinct Islands
    • 131. Palindrome Partitioning (M)
    • 967. Numbers With Same Consecutive Differences (M)
    • 79. Word Search (M)
    • 212. Word Search II (M)
    • 472. Concatenated Words （H）
    • Page 2
    • 291. Word Pattern II
    • 17. Letter Combinations of a Phone Number (M)
  • 5.LinkedList
    • Summary
      • 单链表的倒数第 k 个节点
      • Merge two/k sorted LinkedList
      • Middle of the Linked List
      • 判断链表是否包含环
      • 两个链表是否相交 Intersection of Two Linked Lists
      • 递归反转链表
      • 如何判断回文链表
    • 599.Insert into a Cyclic Sorted List
    • 21.Merge Two Sorted Lists (E)
    • 23.Merge k Sorted Lists (H)
    • 105.Copy List with Random Pointer
    • 141.Linked List Cycle (E)
    • 142.Linked List Cycle II (M)
    • 148.Sort List (M)
    • 86.Partition List (M)
    • 83.Remove Duplicates from Sorted List(E)
    • 82.Remove Duplicates from Sorted List II (M)
    • 206.Reverse Linked List (E)
    • 92.Reverse Linked List II (M)
    • 143.Reorder List (M)
    • 19.Remove Nth Node From End of List (E)
    • 170.Rotate List
    • 🤔25.Reverse Nodes in k-Group (H)
    • 452.Remove Linked List Elements
    • 167.Add Two Numbers
    • 221.Add Two Numbers II
    • 876. Middle of the Linked List (E)
    • 160. Intersection of Two Linked Lists (E)
    • 234. Palindrome Linked List (E)
    • 2130. Maximum Twin Sum of a Linked List (M)
  • 6.Array
    • Summary
      • 前缀和思路PrefixSum
      • 差分数组 Difference Array
      • 双指针Two Pointers
      • 滑动窗口算法算法
      • Sliding windows II
      • 二分搜索Binary Search
      • 排序算法
      • 快速选择算法
    • 604.Window Sum
    • 138.Subarray Sum
    • 41.Maximum Subarray
    • 42.Maximum Subarray II
    • 43.Maximum Subarray III
    • 620.Maximum Subarray IV
    • 621.Maximum Subarray V
    • 6.Merge Two Sorted Arrays
    • 88.Merge Sorted Array
    • 547.Intersection of Two Arrays
    • 548.Intersection of Two Arrays II
    • 139.Subarray Sum Closest
    • 65.Median of two Sorted Arrays
    • 636.132 Pattern
    • 402.Continuous Subarray Sum
    • 303. Range Sum Query - Immutable (E)
    • 304.Range Sum Query 2D - Immutable (M)
    • 560. Subarray Sum Equals K (M)
    • 370. Range Addition（M）
    • 1109. Corporate Flight Bookings(M)
    • 1094. Car Pooling (M)
    • 76. Minimum Window Substring(H)
    • 567. Permutation in String (M)
    • 438. Find All Anagrams in a String(M)
    • 3. Longest Substring Without Repeating Characters (M)
    • 380. Insert Delete GetRandom O(1) (M)
    • 710. Random Pick with Blacklist (H)
    • 528. Random Pick with Weight (M)
    • 26. Remove Duplicates from Sorted Array (E)
    • 27. Remove Element (E)
    • 283. Move Zeroes (E)
    • 659. Split Array into Consecutive Subsequences (M)
    • 4. Median of Two Sorted Arrays (H)
    • 48. Rotate Image (M)
    • 54. Spiral Matrix (M)
    • 59. Spiral Matrix II (M)
    • 918. Maximum Sum Circular Subarray
    • 128. Longest Consecutive Sequence (M)
    • 238. Product of Array Except Self (M)
    • 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (M)
    • 1151. Minimum Swaps to Group All 1's Together (M)
    • 2134. Minimum Swaps to Group All 1's Together II
    • 2133. Check if Every Row and Column Contains All Numbers
    • 632. Smallest Range Covering Elements from K Lists (H)
    • 36. Valid Sudoku (M)
    • 383. Ransom Note
    • 228. Summary Ranges
  • 7.Two pointers
    • Summary
      • Two Sum
      • 2Sum 3Sum 4Sum 问题
    • 1.Two Sum I
    • 170.Two Sum III - Data structure design
    • 167.Two Sum II- Input array is sorted
    • 609.Two Sum - Less than or equal to target
    • 610.Two Sum - Difference equals to targe
    • 587.Two Sum - Unique pairs
    • 533.Two Sum - Closest to target
    • 443.Two Sum - Greater than target
    • 653. Two Sum IV - Input is a BST (M)
    • 57.3Sum
    • 59.3Sum Closest
    • 58.4Sum
    • 148.Sort Colors
    • 143.Sort Colors II
    • 31.Partition Array
    • 625.Partition Array II
    • 382.Triangle Count
      • 611. Valid Triangle Number
    • 521.Remove Duplicate Numbers in Array
    • 167. Two Sum II - Input Array Is Sorted (E)
    • 870. Advantage Shuffle (M)
    • 9. Palindrome Number (E)
    • 125. Valid Palindrome(E)
    • 5. Longest Palindromic Substring (M)
    • 42. Trapping Rain Water
    • 11. Container With Most Water (M)
    • 658. Find K Closest Elements (M)
    • 392. Is Subsequence
  • 8.Data Structure
    • Summary
      • 数据结构的存储方式
      • 单调栈
      • 单调队列
      • 二叉堆 Binary Heap
      • TreeMap
      • TreeSet
      • 🌟Trie
      • Trie Application
    • 155. Min Stack (E)
    • 716. Max Stack (E)
    • 1648. Sell Diminishing-Valued Colored Balls
    • 232. Implement Queue using Stacks (E)
    • 225. Implement Stack using Queues(E)
    • 84.Largest Rectangle in Histogram
    • 128.Hash Function
    • Max Tree
    • 544.Top k Largest Numbers
    • 545.Top k Largest Numbers II
    • 613.High Five
    • 606.Kth Largest Element II
    • 5.Kth Largest Element
    • 129.Rehashing
    • 4.Ugly Number II
    • 517.Ugly Number
    • 28. Implement strStr()
    • 594.strStr II
    • 146.LRU Cache
    • 460.LFU Cache
    • 486.Merge k Sorted Arrays
    • 130.Heapify
    • 215. Kth Largest Element in an Array (M)
    • 612.K Closest Points
    • 692. Top K Frequent Words
    • 347.Top K Frequent Elements
    • 601.Flatten 2D Vector
    • 540.Zigzag Iterator
    • 541.Zigzag Iterator II
    • 423.Valid Parentheses
    • 488.Happy Number
    • 547.Intersection of Two Arrays
    • 548.Intersection of Two Arrays II
    • 627.Longest Palindrome
    • 638.Strings Homomorphism
    • 138.Subarray Sum
    • 647.Substring Anagrams
    • 171.Anagrams
    • 739. Daily Temperatures(M)
    • 496. Next Greater Element I (E)
    • 503. Next Greater Element II（M）
    • 316. Remove Duplicate Letters(M) & 1081. Smallest Subsequence of Distinct Characters
    • 239. Sliding Window Maximum (H)
    • 355. Design Twitter (M)
    • 895. Maximum Frequency Stack (H)
    • 20. Valid Parentheses (E)
    • 921. Minimum Add to Make Parentheses Valid (M)
    • 1541. Minimum Insertions to Balance a Parentheses String (M)
    • 32. Longest Valid Parentheses (H)
    • Basic Calculator (*)
      • 224. Basic Calculator
      • 227. Basic Calculator II (M)
    • 844. Backspace String Compare
    • 295. Find Median from Data Stream
    • 208. Implement Trie (Prefix Tree)
    • 461.Kth Smallest Numbers in Unsorted Array
    • 1152.Analyze user website visit pattern
    • 811. Subdomain Visit Count (M)
    • 71. Simplify Path (M)
    • 362. Design Hit Counter
  • 9.Dynamic Programming
    • Summary
      • 最优子结构 Optimal Sustructure
      • 子序列解题模板
      • 空间压缩
      • 背包问题
        • Untitled
      • 股票买卖问题
      • KMP
    • 109.Triangle
    • 110.Minimum Path Sum
    • 114.Unique Paths
    • 115.Unique Paths II
    • 70.Climbing Stairs
    • 272.Climbing StairsII
    • 116.Jump Game
    • 117.Jump Game II
    • 322.Coin Change
    • 518. Coin Change 2 ()
    • Backpack I~VI
      • LintCode 563.Backpack V (M)
    • Best Time to Buy and Sell Stock（*）
      • 121. Best Time to Buy and Sell Stock
      • 122. Best Time to Buy and Sell Stock II (M)
      • 123. Best Time to Buy and Sell Stock III (H)
      • 188. Best Time to Buy and Sell Stock IV (H)
      • 309. Best Time to Buy and Sell Stock with Cooldown (M)
      • 714. Best Time to Buy and Sell Stock with Transaction Fee (M)
    • 394.Coins in a line
    • 395.Coins in a Line II
    • 509. Fibonacci Number (E)
    • 931. Minimum Falling Path Sum (M)
    • 494. Target Sum (M)
    • 72. Edit Distance (H)
    • 300.Longest Increasing Subsequence
    • 1143. Longest Common Subsequence (M)
    • 718. Maximum Length of Repeated Subarray
    • 583. Delete Operation for Two Strings (M)
    • 712. Minimum ASCII Delete Sum for Two Strings(M)
    • 53. Maximum Subarray (E)
    • 516. Longest Palindromic Subsequence (M)
    • 1312. Minimum Insertion Steps to Make a String Palindrome (H)
    • 416. Partition Equal Subset Sum (M)
    • 64. Minimum Path Sum(M)
    • 651. 4 Keys Keyboards (M)
    • House Robber (*)
      • 198. House Robber (M)
      • 213. House Robbber II
      • 337. House Robber III (M)
    • Word Break (*)
      • 139.Word Break (M)
    • 140. Word Break II (H)
    • 828. Count Unique Characters of All Substrings of a Given String (H)
    • 174. Dungeon Game (H)
    • 1567. Maximum Length of Subarray With Positive Product (M)
  • 10. Graph
    • Introduction
      • 有向图的环检测
      • 拓扑排序
      • 二分图判定
      • Union-Find
      • 最小生成树（Minimum Spanning Tree）算法
        • KRUSKAL 最小生成树算法
        • Prim 最小生成树算法
      • Dijkstra 最短路径算法
      • BFS vs DFS
    • 797. All Paths From Source to Target (M)
    • 785. Is Graph Bipartite? (M)
    • 886. Possible Bipartition (M)
    • 130. Surrounded Regions (M)
    • 990. Satisfiability of Equality Equations (M)
    • 721. Accounts Merge (M)
    • 323. Number of Connected Components in an Undirected Graph (M)
    • 261. Graph Valid Tree
    • 1135. Connecting Cities With Minimum Cost
    • 1584. Min Cost to Connect All Points (M)
    • 277. Find the Celebrity (M)
    • 743. Network Delay Time (M)
    • 1631. Path With Minimum Effort (M)
    • 1514. Path with Maximum Probability (M)
    • 589.Connecting Graph
    • 🌟787. Cheapest Flights Within K Stops (M)
    • 2050. Parallel Courses III (H)
    • 1293. Shortest Path in a Grid with Obstacles Elimination (H)
    • 864. Shortest Path to Get All Keys (H)
    • 269. Alien Dictionary (H)
    • 1192. Critical Connections in a Network (H)
    • 529. Minesweeper (M)
  • 11.Math
    • Page 1
Powered by GitBook
On this page
  • 1.Description(Medium)
  • Notice
  • 2.Code

Was this helpful?

  1. 8.Data Structure

5.Kth Largest Element

Previous606.Kth Largest Element IINext129.Rehashing

Last updated 5 years ago

Was this helpful?

1.Description(Medium)

Find K-th largest element in an array.

Notice

You can swap elements in the array

Have you met this question in a real interview?

Yes

Example

In array[9,3,2,4,8], the 3rd largest element is4.

In array[1,2,3,4,5], the 1st largest element is5, 2nd largest element is4, 3rd largest element is3and etc.

O(n) time, O(1) extra memory.

2.Code

Challenge
Tags
Sort
Quick Sort
https://aaronice.gitbooks.io/lintcode/content/data_structure/kth_largest_element.html