代码
return segmentItem{candidate: i.candidate, count: i.count + j.count} }
if i.count > j.count { return segmentItem{candidate: i.candidate, count: i.count - j.count}
} return segmentItem{candidate: j.candidate, count: j.count - i.count}
}
直到根节点的 candidate 和 count 都填满。注意,这里的 count 并不是元素出现的总次数,而是摩尔投票中坚持没有被投出去的轮数。当线段树构建完成以后,就可以开始查询任意区间内的众数
了,candidate 即为众数。接下来还要确定众数是否满足 threshold 的条件。
用一个字典记录每个元素在数组中出现位置的下标,例如上述这个例子,用 map 记录下标:
count = map[1:[0 1 4 5] 2:[2 3]]。由于下标在记录过程中是递增的,所以满足二分查找的条件。
利用这个字典就可以查出在任意区间内,指定元素出现的次数。例如这里要查找 1 在 [0,5] 区间内出现的个数,那么利用 2 次二分查找,分别找到 lowerBound 和 upperBound,在
[lowerBound,upperBound) 区间内,都是元素 1,那么区间长度即是该元素重复出现的次数,和 threshold 比较,如果 ≥ threshold 说明找到了答案,否则没有找到就输出 -1。
代码
package leetcode
import ( "sort"
)
type segmentItem struct { candidate int
countint }
// MajorityChecker define type MajorityChecker struct {
segmentTree []segmentItem data[]int
mergefunc(i, j segmentItem) segmentItem countmap[int][]int
}
// Constructor1157 define func Constructor1157(arr []int) MajorityChecker {
data, tree, mc, count := make([]int, len(arr)), make([]segmentItem, 4*len(arr)), MajorityChecker{}, make(map[int][]int)
} if i.count > j.count {
return segmentItem{candidate: i.candidate, count: i.count - j.count} }
return segmentItem{candidate: j.candidate, count: j.count - i.count} }
for i := 0; i < len(arr); i++ { data[i] = arr[i]
} for i := 0; i < len(arr); i++ {
if _, ok := count[arr[i]]; !ok { count[arr[i]] = []int{}
} count[arr[i]] = append(count[arr[i]], i)
} mc.data, mc.segmentTree, mc.count = data, tree, count
if len(arr) > 0 { mc.buildSegmentTree(0, 0, len(arr)-1)
} return mc
}
func (mc *MajorityChecker) buildSegmentTree(treeIndex, left, right int) { if left == right {
mc.segmentTree[treeIndex] = segmentItem{candidate: mc.data[left], count:
1} return
} leftTreeIndex, rightTreeIndex := mc.leftChild(treeIndex),
mc.rightChild(treeIndex)
midTreeIndex := left + (right-left)>>1 mc.buildSegmentTree(leftTreeIndex, left, midTreeIndex)
mc.buildSegmentTree(rightTreeIndex, midTreeIndex+1, right)
mc.segmentTree[treeIndex] = mc.merge(mc.segmentTree[leftTreeIndex], mc.segmentTree[rightTreeIndex])
}
func (mc *MajorityChecker) leftChild(index int) int { return 2*index + 1
}
func (mc *MajorityChecker) rightChild(index int) int { return 2*index + 2
} return segmentItem{candidate: -1, count: -1}
}
func (mc *MajorityChecker) queryInTree(treeIndex, left, right, queryLeft, queryRight int) segmentItem {
midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1, mc.leftChild(treeIndex), mc.rightChild(treeIndex)
if queryLeft <= left && queryRight >= right { // segment completely inside range
return mc.segmentTree[treeIndex] }
if queryLeft > midTreeIndex { return mc.queryInTree(rightTreeIndex, midTreeIndex+1, right, queryLeft,
queryRight)
} else if queryRight <= midTreeIndex { return mc.queryInTree(leftTreeIndex, left, midTreeIndex, queryLeft,
queryRight)
} // merge query results
return mc.merge(mc.queryInTree(leftTreeIndex, left, midTreeIndex, queryLeft, midTreeIndex),
mc.queryInTree(rightTreeIndex, midTreeIndex+1, right, midTreeIndex+1, queryRight))
}
// Query define func (mc *MajorityChecker) Query(left int, right int, threshold int) int {
res := mc.query(left, right)
if _, ok := mc.count[res.candidate]; !ok { return -1
} start := sort.Search(len(mc.count[res.candidate]), func(i int) bool { return
left <= mc.count[res.candidate][i] })
end := sort.Search(len(mc.count[res.candidate]), func(i int) bool { return right < mc.count[res.candidate][i] }) - 1
if (end - start + 1) >= threshold { return res.candidate
} return -1
}
/**
- Your MajorityChecker object will be instantiated and called as such:
- obj := Constructor(arr);
全站分卷索引 · 462 卷
- 1532. K-diff Pairs in an Array
- 2题目大意
- 3537. Complex Number Multiplication
- 4541. Reverse String II
- 5解题思路
- 6题目大意
- 7代码
- 8547. Friend Circles
- 9解题思路
- 10557. Reverse Words in a String III
- 11代码
- 12题目大意
- 13题目
- 14566. Reshape the Matrix
- 15题目大意
- 16代码
- 17题目大意
- 18572. Subtree of Another Tree
- 19题目大意
- 20575. Distribute Candies
- 21题目大意
- 22解题思路
- 23题目大意
- 24代码
- 25题目大意
- 26628. Maximum Product of Three Numbers
- 27632. Smallest Range Covering Elements from K Lists
- 28代码
- 29633. Sum of Square Numbers
- 30解题思路
- 31题目大意
- 32代码
- 33637. Average of Levels in Binary Tree
- 34638. Shopping Offers
- 35题目大意
- 36解题思路
- 37645. Set Mismatch
- 38题目大意
- 39648. Replace Words
- 40653. Two Sum IV - Input is a BST
- 41题目大意
- 42题目大意
- 43代码
- 44题目大意
- 45662. Maximum Width of Binary Tree
- 46题目大意
- 47代码
- 48668. Kth Smallest Number in Multiplication Table
- 49题目大意
- 50676. Implement Magic Dictionary
- 51题目大意
- 52682. Baseball Game
- 53题目大意
- 54684. Redundant Connection
- 55题目大意
- 56解题思路
- 57题目大意
- 58代码
- 59693. Binary Number with Alternating Bits
- 60题目大意
- 61695. Max Area of Island
- 62题目大意
- 63697. Degree of an Array
- 64代码
- 65题目大意
- 66解题思路
- 67代码
- 68704. Binary Search
- 69代码
- 70题目大意
- 71706. Design HashMap
- 72题目大意
- 73707. Design Linked List
- 74题目大意
- 75710. Random Pick with Blacklist
- 76题目大意
- 77代码
- 78713. Subarray Product Less Than K
- 79代码
- 80题目大意
- 81715. Range Module
- 82题目大意
- 83717. 1-bit and 2-bit Characters
- 84题目大意
- 85题目大意
- 86719. Find K-th Smallest Pair Distance
- 87题目大意
- 88720. Longest Word in Dictionary
- 89题目大意
- 90721. Accounts Merge
- 91题目大意
- 92代码
- 93725. Split Linked List in Parts
- 94题目大意
- 95726. Number of Atoms
- 96题目大意
- 97解题思路
- 98729. My Calendar I
- 99题目大意
- 100解题思路
- 101732. My Calendar III
- 102题目大意
- 103解题思路
- 104733. Flood Fill
- 105解题思路
- 106题目
- 107题目大意
- 108739. Daily Temperatures
- 109744. Find Smallest Letter Greater Than Target
- 110题目大意
- 111745. Prefix and Suffix Search
- 112解题思路
- 113746. Min Cost Climbing Stairs
- 114题目大意
- 115748. Shortest Completing Word
- 116题目大意
- 117753. Cracking the Safe
- 118题目大意
- 119756. Pyramid Transition Matrix
- 120题目大意
- 121代码
- 122题目大意
- 123763. Partition Labels
- 124解题思路
- 125765. Couples Holding Hands
- 126题目大意
- 127代码
- 128题目大意
- 129767. Reorganize String
- 130代码
- 131771. Jewels and Stones
- 132代码
- 133题目大意
- 134代码
- 135781. Rabbits in Forest
- 136题目大意
- 137784. Letter Case Permutation
- 138786. K-th Smallest Prime Fraction
- 139题目大意
- 140793. Preimage Size of Factorial Zeroes Function
- 141解题思路
- 142代码
- 143802. Find Eventual Safe States
- 144解题思路
- 145题目大意
- 146解题思路
- 147811. Subdomain Visit Count
- 148题目
- 149解题思路
- 150812. Largest Triangle Area
- 151题目大意
- 152815. Bus Routes
- 153代码
- 154817. Linked List Components
- 155解题思路
- 156819. Most Common Word
- 157题目大意
- 158826. Most Profit Assigning Work
- 159代码
- 160828. Unique Letter String
- 161代码
- 162832. Flipping an Image
- 163题目大意
- 164题目大意
- 165836. Rectangle Overlap
- 166解题思路
- 167题目大意
- 168839. Similar String Groups
- 169题目大意
- 170841. Keys and Rooms
- 171题目大意
- 172842. Split Array into Fibonacci Sequence
- 173题目大意
- 174844. Backspace String Compare
- 175题目大意
- 176845. Longest Mountain in Array
- 177题目大意
- 178850. Rectangle Area II
- 179题目大意
- 180代码
- 181851. Loud and Rich
- 182题目大意
- 183解题思路
- 184852. Peak Index in a Mountain Array
- 185解题思路
- 186853. Car Fleet
- 187题目大意
- 188856. Score of Parentheses
- 189题目大意
- 190862. Shortest Subarray with Sum at Least K
- 191题目大意
- 192863. All Nodes Distance K in Binary Tree
- 193题目大意
- 194代码
- 195864. Shortest Path to Get All Keys
- 196解题思路
- 197867. Transpose Matrix
- 198872. Leaf-Similar Trees
- 199题目大意
- 200代码
- 201题目大意
- 202876. Middle of the Linked List
- 203题目大意
- 204878. Nth Magical Number
- 205题目大意
- 206880. Decoded String at Index
- 207题目大意
- 208881. Boats to Save People
- 209解题思路
- 210题目大意
- 211885. Spiral Matrix III
- 212题目大意
- 213887. Super Egg Drop
- 214题目大意
- 215代码
- 216题目
- 217解题思路
- 218891. Sum of Subsequence Widths
- 219代码
- 220题目大意
- 221895. Maximum Frequency Stack
- 222题目大意
- 223解题思路
- 224896. Monotonic Array
- 225题目大意
- 226897. Increasing Order Search Tree
- 227解题思路
- 228898. Bitwise ORs of Subarrays
- 229题目大意
- 230代码
- 231901. Online Stock Span
- 232题目大意
- 233904. Fruit Into Baskets
- 234题目大意
- 235907. Sum of Subarray Minimums
- 236代码
- 237911. Online Election
- 238解题思路
- 239914. X of a Kind in a Deck of Cards
- 240题目大意
- 241918. Maximum Sum Circular Subarray
- 242题目大意
- 243代码
- 244题目大意
- 245代码
- 246921. Minimum Add to Make Parentheses Valid
- 247题目大意
- 248题目大意
- 249题目
- 250924. Minimize Malware Spread
- 251题目大意
- 252解题思路
- 253925. Long Pressed Name
- 254题目大意
- 255927. Three Equal Parts
- 256题目大意
- 257928. Minimize Malware Spread II
- 258题目大意
- 259解题思路
- 260930. Binary Subarrays With Sum
- 261代码
- 262题目大意
- 263942. DI String Match
- 264代码
- 265题目大意
- 266题目
- 267代码
- 268题目大意
- 269952. Largest Component Size by Common Factor
- 270题目大意
- 271代码
- 272953. Verifying an Alien Dictionary
- 273题目大意
- 274959. Regions Cut By Slashes
- 275题目大意
- 276代码
- 277961. N-Repeated Element in Size 2N Array
- 278代码
- 279题目大意
- 280代码
- 281969. Pancake Sorting
- 282题目大意
- 283970. Powerful Integers
- 284题目大意
- 285973. K Closest Points to Origin
- 286题目大意
- 287976. Largest Perimeter Triangle
- 288题目大意
- 289题目大意
- 290978. Longest Turbulent Subarray
- 291题目大意
- 292979. Distribute Coins in Binary Tree
- 293题目大意
- 294代码
- 295980. Unique Paths III
- 296题目大意
- 297981. Time Based Key-Value Store
- 298题目大意
- 299解题思路
- 300984. String Without AAA or BBB
- 301题目大意
- 302985. Sum of Even Numbers After Queries
- 303题目大意
- 304986. Interval List Intersections
- 305代码
- 306题目大意
- 307解题思路
- 308题目
- 309代码
- 310993. Cousins in Binary Tree
- 311题目大意
- 312解题思路
- 313995. Minimum Number of K Consecutive Bit Flips
- 314题目大意
- 315代码
- 316996. Number of Squareful Arrays
- 317代码
- 318999. Available Captures for Rook
- 319题目大意
- 320解题思路
- 3211002. Find Common Characters
- 3221003. Check If Word Is Valid After Substitutions
- 323题目大意
- 324解题思路
- 3251004. Max Consecutive Ones III
- 3261005. Maximize Sum Of Array After K Negations
- 327题目大意
- 3281011. Capacity To Ship Packages Within D Days
- 329题目大意
- 3301017. Convert to Base -2
- 331解题思路
- 332题目大意
- 3331020. Number of Enclaves
- 334题目大意
- 3351021. Remove Outermost Parentheses
- 336题目大意
- 337代码
- 3381025. Divisor Game
- 339代码
- 340题目大意
- 341解题思路
- 342题目大意
- 343解题思路
- 3441030. Matrix Cells in Distance Order
- 345题目大意
- 346代码
- 347题目大意
- 348题目大意
- 349代码
- 3501047. Remove All Adjacent Duplicates In String
- 351题目大意
- 3521049. Last Stone Weight II
- 353代码
- 354题目大意
- 3551052. Grumpy Bookstore Owner
- 356解题思路
- 3571054. Distant Barcodes
- 358题目大意
- 3591073. Adding Two Negabinary Numbers
- 360题目大意
- 361代码
- 3621074. Number of Submatrices That Sum to Target
- 363解题思路
- 3641078. Occurrences After Bigram
- 365解题思路
- 366题目大意
- 3671089. Duplicate Zeros
- 3681093. Statistics from a Large Sample
- 369题目大意
- 3701105. Filling Bookcase Shelves
- 371题目大意
- 3721108. Defanging an IP Address
- 373代码
- 374题目大意
- 3751111. Maximum Nesting Depth of Two Valid Parentheses Strings
- 376题目大意
- 377代码
- 3781122. Relative Sort Array
- 379解题思路
- 3801123. Lowest Common Ancestor of Deepest Leaves
- 381题目大意
- 3821128. Number of Equivalent Domino Pairs
- 383解题思路
- 384题目大意
- 3851145. Binary Tree Coloring Game
- 386题目大意
- 387解题思路
- 3881154. Day of the Year
- 389题目大意
- 390题目
- 391解题思路
- 392代码
- 3931160. Find Words That Can Be Formed by Characters
- 394解题思路
- 395题目大意
- 396代码
- 397题目大意
- 3981175. Prime Arrangements
- 399题目大意
- 4001184. Distance Between Bus Stops
- 401题目大意
- 402解题思路
- 403题目大意
- 404题目
- 405代码
- 406题目大意
- 4071201. Ugly Number III
- 408解题思路
- 409题目大意
- 410解题思路
- 4111207. Unique Number of Occurrences
- 4121208. Get Equal Substrings Within Budget
- 413题目大意
- 4141217. Play with Chips
- 415题目大意
- 416题目
- 417代码
- 418题目大意
- 419解题思路
- 420题目大意
- 421代码
- 422题目大意
- 4231252. Cells with Odd Values in a Matrix
- 424题目大意
- 425解题思路
- 4261254. Number of Closed Islands
- 427题目大意
- 4281260. Shift 2D Grid
- 429题目大意
- 430代码
- 431题目大意
- 432题目大意
- 433代码
- 4341281. Subtract the Product and Sum of Digits of an Integer
- 4351283. Find the Smallest Divisor Given a Threshold
- 436题目大意
- 4371287. Element Appearing More Than 25% In Sorted Array
- 4381290. Convert Binary Number in a Linked List to Integer
- 439题目大意
- 440题目大意
- 4411299. Replace Elements with Greatest Element on Right Side
- 4421300. Sum of Mutated Array Closest to Target
- 443解题思路
- 4441302. Deepest Leaves Sum
- 4451304. Find N Unique Integers Sum up to Zero
- 446解题思路
- 447题目大意
- 448解题思路
- 449题目大意
- 4501313. Decompress Run-Length Encoded List
- 451解题思路
- 452题目大意
- 4531380. Lucky Numbers in a Matrix
- 454题目大意
- 4551385. Find the Distance Value Between Two Arrays
- 456题目大意
- 4571389. Create Target Array in the Given Order
- 458题目大意
- 459题目大意
- 460题目大意
- 4611470. Shuffle the Array
- 462解题思路