双十一的购物车

[编程题]双十一的购物车

热度指数：373 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

SS是途虎养车的一名技术人员，她每年双11的时候，会尝试清空自己购物车中“看起来便宜”的商品。她的购物车列表是有序的，如果一件商品，其价格比购物车中前一个商品和后一个商品的价格都低，则SS认为这件商品“看起来便宜”。

有一天，你趁她午睡且忘记锁屏登入了她的购物网站账号，想通过调整购物车顺序，来“帮助”她买到最多的的商品。

示例1

输入

[1,2,3]

输出

说明

输入是一个整型数组，代表A现在购物车中的商品价格。输出经过重新排列之后，SS最多会购买的商品数量。示例中SS最多会购买1件商品（一个可能的排列为[3,1,2]）

备注:

1. 在本题中，最多是指个数上最多；
2. 第一个和最后一个商品，不符合“看起来便宜”的定义。

算法知识视频讲解

牛客652076208号

如果在没有重复数值的条件下只需要指定len的长度就可以得解

int reorder(int* prices, int pricesLen ) {

int flag = 0;

if(pricesLen%2==0)

flag=-1 ;

return pricesLen / 2 + (flag) ;

}

如果有重复的数值，需要特殊对待

主要观察最中间的数值的情况

中间数值在右边的连续个数，并减去上结果

int reorder(int* prices, int pricesLen ) {
    int flag = 0;
    if(pricesLen%2==0)
        flag=-1 ;
    if(prices[pricesLen/2]==prices[pricesLen/2-1])
        for(int i=pricesLen/2+1;i<pricesLen;i++){
                if(prices[pricesLen/2]==prices[i])
                    flag --;
            }
    return pricesLen / 2 + (flag) ;
}

发表于 2021-09-06 01:23:40 回复(0)

别的不会就会做题

先说明一下，给出的测试数据不一定是有序的，虽然题目中说是有序的……

思路就是将peices分成较小和较大两个部分，然后将较小的元素插入两个较大元素的中间，我们只需要比较一个较小元素插入位置左边的较大元素就行

原因是，该较小元素本身就小于等于插入位置左边的元素，如果二者相等，那么肯定不满足题意，反之如果小于，那么插入位置右边的元素本身就大于等于插入位置左边的元素，这样就符合题意

最后注意的是偶数的情况，最后一个较小元素是插入在最后面，它没办法成为满足题意，因为它右边没有元素了，所以需要考虑这种情况

import java.util.*;
 
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param prices int整型一维数组 购物车中的商品价格列表
     * @return int整型
     */
    public int reorder (int[] prices)
    {
        Arrays.sort(prices);
        int n = prices.length;
        int m = n / 2;
        int answer = m;
        for (int i = 0; i < m; i++)
            if (prices[i] == prices[i + m])
                answer--;
        if (n % 2 == 0 && prices[m - 1] < prices[m * 2 - 1])
            answer--;
        return answer;
    }
}

发表于 2025-01-26 21:01:53 回复(0)