Press "Enter" to skip to content

Posts published in “Array”

花花酱 307. Range Sum Query – Mutable

题目大意:给你一个数组,让你求一个范围之内所有元素的和,数组元素可以更改。

Problem:

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Note:

  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly.

Idea:

Fenwick Tree

Solution:

C++

Time complexity:

init O(nlogn)

query: O(logn)

update: O(logn)

C++

Java

Python3

Solution 2: Segment Tree

C++

花花酱 LeetCode 748. Largest Number At Least Twice of Others

题目大意:给你一个数组,问你其中最大的数是不是比剩下的数大2倍以上,返回这样的数的索引。如果不存在,返回-1.

Problem:

In a given integer array nums, there is always exactly one largest element.

Find whether the largest element in the array is at least twice as much as every other number in the array.

If it is, return the index of the largest element, otherwise return -1.

Example 1:

Example 2:

Note:

  1. nums will have a length in the range [1, 50].
  2. Every nums[i] will be an integer in the range [0, 99].

Solution:

C++

 

花花酱 LeetCode 744. Find Smallest Letter Greater Than Target

Problem:

Given a list of sorted characters letters containing only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.

Letters also wrap around. For example, if the target is target = 'z' and letters = ['a', 'b'], the answer is 'a'.

Examples:

Note:

  1. letters has a length in range [2, 10000].
  2. letters consists of lowercase letters, and contains at least 2 unique letters.
  3. target is a lowercase letter.

Link: https://leetcode.com/problems/find-smallest-letter-greater-than-target/description/ 

Idea:

  1. Scan the array Time complexity: O(n)
  2. Binary search Time complexity: O(logn)

Solution 1:

C++ / Scan

C++ / Set

C++ / Binary Search

 

花花酱 LeetCode 164. Maximum Gap

https://leetcode.com/problems/maximum-gap/description/

Problem:

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

题目大意:

给你一个没有排序的正整数数组。输出排序后,相邻元素的差的最大值(Max Gap)。需要在线性时间内解决。

Example:

Input:  [5, 0, 4, 2, 12, 10]

Output: 5

Explanation: 

Sorted: [0, 2, 4, 5, 10, 12]

max gap is 10 – 5 = 5

Idea:

Bucket sort. Use n buckets to store all the numbers. For each bucket, only track the min / max value.

桶排序。用n个桶来存放数字。对于每个桶,只跟踪存储最大值和最小值。

max gap must come from two “adjacent” buckets, b[i], b[j], j > i, b[i+1] … b[j – 1] must be empty.

max gap 只可能来自”相邻”的两个桶 b[i] 和 b[j], j > i, b[i] 和 b[j] 之间的桶(如果有)必须为空。

max gap = b[j].min – b[i].min

Time complexity: O(n)

时间复杂度: O(n)

Space complexity: O(n)

空间复杂度: O(n)

Solution:

C++