Skip to content

Files

Latest commit

c29b144 · May 17, 2024

History

History
This branch is 603 commits behind doocs/leetcode:main.

1409.Queries on a Permutation With Key

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
May 17, 2024
May 17, 2024
Aug 13, 2022
Aug 5, 2022
Aug 5, 2022
Aug 5, 2022
Jan 13, 2024
Jan 13, 2024
Jan 13, 2024
Jan 13, 2024
comments difficulty edit_url rating source tags
true
中等
1334
第 184 场周赛 Q2
树状数组
数组
模拟

English Version

题目描述

给定一个正整数数组 queries ,其取值范围在 1m 之间。 请你根据以下规则按顺序处理所有 queries[i](从 i=0i=queries.length-1):

  • 首先,你有一个排列 P=[1,2,3,...,m]
  • 对于当前的 i ,找到 queries[i] 在排列 P 中的位置(从 0 开始索引),然后将它移到排列 P 的开头(即下标为 0 处)。注意, queries[i] 的查询结果是 queries[i]P 中移动前的位置。

返回一个数组,包含从给定  queries 中查询到的结果。

 

示例 1:

输入:queries = [3,1,2,1], m = 5
输出:[2,1,2,1] 
解释:处理 queries 的过程如下:
对于 i=0: queries[i]=3, P=[1,2,3,4,5], 3 在 P 中的位置是 2,然后我们把 3 移动到 P 的开头,得到 P=[3,1,2,4,5] 。
对于 i=1: queries[i]=1, P=[3,1,2,4,5], 1 在 P 中的位置是 1,然后我们把 1 移动到 P 的开头,得到 P=[1,3,2,4,5] 。 
对于 i=2: queries[i]=2, P=[1,3,2,4,5], 2 在 P 中的位置是 2,然后我们把 2 移动到 P 的开头,得到 P=[2,1,3,4,5] 。
对于 i=3: queries[i]=1, P=[2,1,3,4,5], 1 在 P 中的位置是 1,然后我们把 1 移动到 P 的开头,得到 P=[1,2,3,4,5] 。 
因此,包含结果的数组为 [2,1,2,1] 。  

示例 2:

输入:queries = [4,1,2,2], m = 4
输出:[3,1,2,0]

示例 3:

输入:queries = [7,5,5,8,3], m = 8
输出:[6,5,0,7,5]

 

提示:

  • 1 <= m <= 10^3
  • 1 <= queries.length <= m
  • 1 <= queries[i] <= m

解法

方法一:模拟

题目数据规模不大,可以直接模拟。

方法一:树状数组

树状数组,也称作“二叉索引树”(Binary Indexed Tree)或 Fenwick 树。 它可以高效地实现如下两个操作:

  1. 单点更新 update(x, delta): 把序列 x 位置的数加上一个值 delta;
  2. 前缀和查询 query(x):查询序列 [1,...x] 区间的区间和,即位置 x 的前缀和。

这两个操作的时间复杂度均为 O ( log n )

树状数组最基本的功能就是求比某点 x 小的点的个数(这里的比较是抽象的概念,可以是数的大小、坐标的大小、质量的大小等等)。

比如给定数组 a[5] = {2, 5, 3, 4, 1},求 b[i] = 位置 i 左边小于等于 a[i] 的数的个数。对于此例,b[5] = {0, 1, 1, 2, 0}

解决方案是直接遍历数组,每个位置先求出 query(a[i]),然后再修改树状数组 update(a[i], 1) 即可。当数的范围比较大时,需要进行离散化,即先进行去重并排序,然后对每个数字进行编号。

Python3

class Solution:
    def processQueries(self, queries: List[int], m: int) -> List[int]:
        p = list(range(1, m + 1))
        ans = []
        for v in queries:
            j = p.index(v)
            ans.append(j)
            p.pop(j)
            p.insert(0, v)
        return ans

Java

class Solution {
    public int[] processQueries(int[] queries, int m) {
        List<Integer> p = new LinkedList<>();
        for (int i = 1; i <= m; ++i) {
            p.add(i);
        }
        int[] ans = new int[queries.length];
        int i = 0;
        for (int v : queries) {
            int j = p.indexOf(v);
            ans[i++] = j;
            p.remove(j);
            p.add(0, v);
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        vector<int> p(m);
        iota(p.begin(), p.end(), 1);
        vector<int> ans;
        for (int v : queries) {
            int j = 0;
            for (int i = 0; i < m; ++i) {
                if (p[i] == v) {
                    j = i;
                    break;
                }
            }
            ans.push_back(j);
            p.erase(p.begin() + j);
            p.insert(p.begin(), v);
        }
        return ans;
    }
};

Go

func processQueries(queries []int, m int) []int {
	p := make([]int, m)
	for i := range p {
		p[i] = i + 1
	}
	ans := []int{}
	for _, v := range queries {
		j := 0
		for i := range p {
			if p[i] == v {
				j = i
				break
			}
		}
		ans = append(ans, j)
		p = append(p[:j], p[j+1:]...)
		p = append([]int{v}, p...)
	}
	return ans
}

方法二

Python3

class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.c = [0] * (n + 1)

    @staticmethod
    def lowbit(x):
        return x & -x

    def update(self, x, delta):
        while x <= self.n:
            self.c[x] += delta
            x += BinaryIndexedTree.lowbit(x)

    def query(self, x):
        s = 0
        while x > 0:
            s += self.c[x]
            x -= BinaryIndexedTree.lowbit(x)
        return s


class Solution:
    def processQueries(self, queries: List[int], m: int) -> List[int]:
        n = len(queries)
        pos = [0] * (m + 1)
        tree = BinaryIndexedTree(m + n)
        for i in range(1, m + 1):
            pos[i] = n + i
            tree.update(n + i, 1)

        ans = []
        for i, v in enumerate(queries):
            j = pos[v]
            tree.update(j, -1)
            ans.append(tree.query(j))
            pos[v] = n - i
            tree.update(n - i, 1)
        return ans

Java

class BinaryIndexedTree {
    private int n;
    private int[] c;

    public BinaryIndexedTree(int n) {
        this.n = n;
        c = new int[n + 1];
    }

    public void update(int x, int delta) {
        while (x <= n) {
            c[x] += delta;
            x += lowbit(x);
        }
    }

    public int query(int x) {
        int s = 0;
        while (x > 0) {
            s += c[x];
            x -= lowbit(x);
        }
        return s;
    }

    public static int lowbit(int x) {
        return x & -x;
    }
}

class Solution {
    public int[] processQueries(int[] queries, int m) {
        int n = queries.length;
        BinaryIndexedTree tree = new BinaryIndexedTree(m + n);
        int[] pos = new int[m + 1];
        for (int i = 1; i <= m; ++i) {
            pos[i] = n + i;
            tree.update(n + i, 1);
        }
        int[] ans = new int[n];
        int k = 0;
        for (int i = 0; i < n; ++i) {
            int v = queries[i];
            int j = pos[v];
            tree.update(j, -1);
            ans[k++] = tree.query(j);
            pos[v] = n - i;
            tree.update(n - i, 1);
        }
        return ans;
    }
}

C++

class BinaryIndexedTree {
public:
    int n;
    vector<int> c;

    BinaryIndexedTree(int _n)
        : n(_n)
        , c(_n + 1) {}

    void update(int x, int delta) {
        while (x <= n) {
            c[x] += delta;
            x += lowbit(x);
        }
    }

    int query(int x) {
        int s = 0;
        while (x > 0) {
            s += c[x];
            x -= lowbit(x);
        }
        return s;
    }

    int lowbit(int x) {
        return x & -x;
    }
};

class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        int n = queries.size();
        vector<int> pos(m + 1);
        BinaryIndexedTree* tree = new BinaryIndexedTree(m + n);
        for (int i = 1; i <= m; ++i) {
            pos[i] = n + i;
            tree->update(n + i, 1);
        }
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            int v = queries[i];
            int j = pos[v];
            tree->update(j, -1);
            ans.push_back(tree->query(j));
            pos[v] = n - i;
            tree->update(n - i, 1);
        }
        return ans;
    }
};

Go

type BinaryIndexedTree struct {
	n int
	c []int
}

func newBinaryIndexedTree(n int) *BinaryIndexedTree {
	c := make([]int, n+1)
	return &BinaryIndexedTree{n, c}
}

func (this *BinaryIndexedTree) lowbit(x int) int {
	return x & -x
}

func (this *BinaryIndexedTree) update(x, delta int) {
	for x <= this.n {
		this.c[x] += delta
		x += this.lowbit(x)
	}
}

func (this *BinaryIndexedTree) query(x int) int {
	s := 0
	for x > 0 {
		s += this.c[x]
		x -= this.lowbit(x)
	}
	return s
}

func processQueries(queries []int, m int) []int {
	n := len(queries)
	pos := make([]int, m+1)
	tree := newBinaryIndexedTree(m + n)
	for i := 1; i <= m; i++ {
		pos[i] = n + i
		tree.update(n+i, 1)
	}
	ans := []int{}
	for i, v := range queries {
		j := pos[v]
		tree.update(j, -1)
		ans = append(ans, tree.query(j))
		pos[v] = n - i
		tree.update(n-i, 1)
	}
	return ans
}